Python 模块之heapq
1、heapq介绍：
堆是非线性的树形的数据结构，有两种堆,最大堆与最小堆。（ heapq库中的堆默认是最小堆）
最大堆，树种各个父节点的值总是大于或等于任何一个子节点的值。
最小堆，树种各个父节点的值总是小于或等于任何一个子节点的值。
我们一般使用二叉堆来实现优先级队列,它的内部调整算法复杂度为logN。
堆是一个二叉树，其中最小堆每个父节点的值都小于或等于其所有子节点的值。
整个最小堆的最小元素总是位于二叉树的根节点。
python的heapq模块提供了对堆的支持。 heapq堆数据结构最重要的特征是heap[0]永远是最小的元素
2、heapq方法介绍：
heappush(heap, item)
heapq.heappush(heap, item) 将item压入到堆数组heap中。如果不进行此步操作，后面的heappop()失效，
会直接返回原列表第一个值，而且必须从头开始heappush，不然也会返回原列表第一个值。例：
a = [12,2,4,5,63,3,2]
heapq.heappush(a,123)
>>>[12, 2, 4, 5, 63, 3, 2, 123]
b = heapq.heappop(a)
>>>12
heappop(heap)
删除并返回最小值，因为堆的特征是heap[0]永远是最小的元素，所以一般都是删除第一个元素。注意，如果不是压入堆中，而是通过append追加一个数值，堆的函数并不能操作这个增加的数值，或者说它堆对来讲是不存在的。
例：
a = []
heapq.heappush(a,11)
heapq.heappush(a,2)
heapq.heappush(a,3)
heapq.heappush(a,4)
a.append(1)
b = heapq.heappop(a)
>>b=2
heapq.heapify(list)
参数必须是list，此函数将list变成堆，实时操作。从而能够在任何情况下使用堆的函数例：
a = [12,2,4,5,63,3,2]
heapq.heapify(a)
heapq.heappop(a)
heapq.heappushpop(heap, item)
是上述heappush和heappop的合体，同时完成两者的功能，注意：相当于先操作了heappush(heap,item)，然后操作heappop(heap)
heapq.heapreplace(heap, item)
是上述heappop和heappush的联合操作。注意：与heappushpop(heap,item)的区别在于，顺序不同，这里是先进行删除，后压入堆
heapq.merge(*iterables)
将多个堆合并a = [2, 4, 6]
b = [1, 3, 5]
c = heapq.merge(a, b)
>>[1, 2, 3, 4, 5, 6]
heapq.nlargest(n, iterable,[ key])
查询堆中的最大n个元素
heapq.nsmallest(n, iterable,[ key])
查询堆中的最小n个元素
优先级的例子和去最大最小的例子可以参考：https://www.cnblogs.com/chimeiwangliang/p/12426753.html （3,4）
以上是 Python 模块之heapq 的全部内容， 来源链接： utcz.com/z/386884.html
