heapq

heapq包提供了高效的堆算法(也称为优先队列算法).

堆, 即一种二叉树结构, 其中每个父结点的值都小于或等于它的两个子结点, 两个子结点之间大小没有要求. 使用数组存储堆结构时, 对于第$i$个结点, 其左右子结点的索引分别为$2i+1$与$2i+2$.

堆分为最大堆和最小堆, heapq提供的是固定的最小堆, 即堆顶元素heap[0]为整个堆中的最小值.

使用方法

创建堆

heapq使用python中的list数据结构来构建堆. 有两种创建堆的方式:

• 初始化一个空的list: [], heapq提供的方法, 如push, pop, replace等方法, 都需要传入一个list, 整个list作为堆来使用

• 使用heapify(list)方法, 将现有的一个list整理成堆

从空堆开始创建

>>> from heapq import *
>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

除了放入纯数字, 可以带入一些业务信息

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

常用方法

参考文档8.4. heapq — Heap queue algorithm.