转载

Python heapq模块官方文档翻译

该模块实现了一个堆队列的算法或者优先级队列算法的实现。

堆是一个任何父节点值都小于等于其子节点的值的二叉树。该应用通过heap[k]<=heap[2*k+1]和heap[k]<=heap[2*k+2]数组来实现，并且从0开始计算元素。为了方便比较，未定义的元素被认为是无穷大的。堆最有意思的属性就是它最小的元素总是根节点，即heap[0]。

下面的API在两个方面和文本堆算法有区别：

a）我们使用从0开始的索引，这使得父节点和其子节点的索引变得更不会那么明显。但由于Python使用的就是基于0的索引，所以这很合适。

b）pop返回最小的值，而不是最大值。（堆队列也被文本中称为“最小堆”，而“最大堆”在文本中更加常见，因为他更加适用于就地排序（in-place sorting））

以上两个区别使得堆看起来就行普通的Python列表：heap[0]为最小项和heap.sort()保持堆不变。

想要创建一个堆，可以通过一个空的列表[]或者通过heapify(）函数来转换一个非空列表。

堆提供了一下方法：

heapq.heappush(heap, item)

给堆新增值，并保持堆不变。

heapq.heappop(heap)

从堆中国返回最小值，并保持堆不变。如果堆为空，则抛出IndexError错误。

如果想要访问堆中最小值，但是又不想弹出它，可通过heap[0]访问。

heapq.heappushpop(heap, item)

相当于分别执行heappush(heap, item)和heappop(heap)，但是比分开执行更加高效。

heapq.heapify(x)

转换一个非空列表x，顺序保持不变（in-place），转换的时间和列表的长度线性相关。

heapq.heapreplace(heap, item)

返回最小值并新增一个值，对的大小保持不变。如果堆是空的，将抛出IndexError异常。

该方法相当于heappop()和heappush()的组合，但是比分开执行更加高效，由于操作完成后堆长度没有改变，其比较适用于固定大小的堆。

需要注意的是，该方法返回的值有可能比新增的值更大，所以如果不希望发生这种情况，可以考虑heappushpop()方法，heappushpop()方法总是返回最小值，但保留更大的值在堆中。

heapq模块还提供了三个堆的一般方法：

heapq.merge(*iterable)

将多个已排序的输入合并成一个已排序的输出（例如从多个日志文件里根据时间戳来合并），并返回一个基于排序值的迭代器。

类似于sorted(itertools.chain(*iterables)) 但是返回的是迭代器，这样避免一次性将所有数据加载到内存中，并且假定每个输入都已经排过序。

heapq.nlargest(n, iterable[,key])

从数据集中返回n个最大值，如果参数中包含key，则指定一个函数作为参数用于从迭代器中的每个元素获取一个对比key：key=str.lower等价于sorted(iterable, key=key, reverse=True)[:n]

heapq.nsmallest(n, iterable[, key])

和nsmallest相反，返回n个最小值

heapq.nlargest(n, iterable[, key])和heapq.nsmallest(n, iteralbe[, key])两个函数当n值较小时，能够提供很好的性能，当n值较大时，使用sorted()函数将会更加高效，当然，如果n==1的时候，使用内置的min()和max()函数将会更加高效。如果这些函数需要被重复使用，则可考虑将迭代器转换成堆。

举例说明：

例一、heapsort函数可以将值一次性推送到堆中，接着一次倒出一个值

>>> 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]

上例和sorted(iterable)类似，但是和sorted()又不一样，因为该实现不是稳定的。

例二、堆的元素可以是元组，当需要在记录上分配对比值（例如任务优先级）时，将会非常有用。