python heapq_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个元素