python中的堆---heapq

import heapq
# python里只有最小堆，如果要用最大堆，每个元素*-1后加入最小堆，然后堆顶元素再*-1即可

# 1，两种方式创建堆
# （1）使用一个空列表，然后使用heapq.heappush()函数把值加入堆中
nums = [2,4,6,1,8]
myheap = []
for i in nums:
    heapq.heappush(myheap, i)
print(‘myheap:‘, myheap) # myheap: [1, 2, 6, 4, 8]


# （2）使用heap.heapify(list)转换列表成为堆结构
nums = [2,4,6,1,8]
heapq.heapify(nums) # 把列表堆化
print(‘nums:‘, nums)  # nums: [1, 2, 6, 4, 8]

# (3)heapq 模块还有一个heapq.merge(*iterables) 方法，
# 用于合并多个排序后的序列成一个排序后的序列， 返回排序后的值的迭代器。

num1 = [2,4,6,1,8]
num2 = [3,5]
num1 = sorted(num1)
num2 = sorted(num2)

res = heapq.merge(num1, num2)
print(‘res:‘, list(res))  # res: [1, 2, 3, 4, 5, 6, 8]

# 2,添加元素

heapq.heappush(nums,10)
heapq.heappush(nums,9)
heapq.heappush(nums,7)
print(nums)


# 3,获取堆顶元素，堆顶元素为最小值
print(nums[0]) #peek,堆顶元素

# 4，删除堆顶元素，修改堆，并且函数返回值为堆顶元素
res = heapq.heappop(nums)
print(res)
# 查看所有元素
print([heapq.heappop(nums) for i in range(len(nums))])
print(nums) # []

# 5，查看长度
print(len(myheap))
# 边删除边遍历
while len(myheap) != 0:
    print(heapq.heappop(myheap))

# 6,删除堆中最小元素并加入一个元素，可以使用heapq.heaprepalce() 函数
nums = [1, 2, 4, 5, 3]
heapq.heapify(nums)
print(‘1:‘, [heapq.heappop(nums) for _ in range(len(nums))]) # 1: [1, 2, 3, 4, 5]

nums = [1, 2, 4, 5, 3]
heapq.heapify(nums)
heapq.heapreplace(nums, 0)
print(‘2:‘, [heapq.heappop(nums) for _ in range(len(nums))]) # 2: [0, 2, 3, 4, 5]

# 7,获取堆前n个最大或最小值，则可以使用heapq.nlargest() 或heapq.nsmallest() 函数
nums = [2,4,6,1,8]
heapq.heapify(nums) # 把列表堆化
print(heapq.nlargest(3, nums)) #[8, 6, 4]
print(heapq.nsmallest(2, nums)) #[1, 2]

# 两个函数还接受一个key参数，用于dict或其他数据结构类型使用
from pprint import pprint # pprint()模块打印出来的数据结构更加完整
portfolio = [
    {‘name‘: ‘IBM‘, ‘shares‘: 100, ‘price‘: 91.1},
    {‘name‘: ‘AAPL‘, ‘shares‘: 50, ‘price‘: 543.22},
    {‘name‘: ‘FB‘, ‘shares‘: 200, ‘price‘: 21.09},
    {‘name‘: ‘HPQ‘, ‘shares‘: 35, ‘price‘: 31.75},
    {‘name‘: ‘YHOO‘, ‘shares‘: 45, ‘price‘: 16.35},
    {‘name‘: ‘ACME‘, ‘shares‘: 75, ‘price‘: 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s[‘price‘])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s[‘price‘])
pprint(cheap)
pprint(expensive)


# 8，自定义比较方法
# python中的堆排序模块heapq本身不支持自定义比较函数，可以通过重写对象的__lt__方法的方式来实现自定义比较函数。
#
# __lt__对应<，当对象之间用<比较大小的时候，就会调用__lt__方法。
# 同样的>会调用__gt__方法，在只重写了__lt__方法的时候，__gt__会对__lt__结果取反。