翻译自heapq — Heap queue algorithm

介绍

这个模块实现了堆队列算法,也被称为优先队列算法。

堆是一个二叉树,其父节点比任何一个子节点都要小。这个实现使用了数组,对于所有大于0的k有heap[k] <= heap[2*k+1]heap[k] <= heap[2*k+2],对于第n层树,其有2^(n-1)个节点,比如第三层二叉树有四个节点。为了比较,不存在的元素将会被认为是无穷大的。堆中有意思的特性是最小的元素总是在树的根部,即heap[0]。

下面的API有两点不同于教科书上的堆算法:

  • 我们的索引从0开始,这样使得父节点和其子节点的关系有所不同,但是这样在Python里更加合适,因为Python里就是索引从0开始。
  • 我们的pop方法会返回最小的元素,而不是最大的,也就是最小堆,最大堆通常在原地排序很有用

这两个使得可以在普通的Python列表中获取堆中元素,heap[0]就是最小的元素,heap.sort()维护堆。

为了创建一个堆,使用列表将其初始化为[],或者你也可以通过heapify()将一个列表转换成堆。

提供下面的方法

  • heappush(heap, item)
  • heappop(heap)
  • heappushpop(heap, item)

将item push到堆里,并且pop出最小的元素,比先执行heappush()然后执行heappop()更有效率

  • heapify(x)
  • heapreplace(heap, item)

pop并且返回最小的元素,并且push一个新的元素,堆的大小不会改变。这个步骤比先执行heappop()然后执行heappush()更有效率,并且在使用一个固定大小的堆会比较合适。这个函数总会返回一个元素,并且以item替换。

返回的元素可能比插入的元素要大,使用heappushpop将会返回一个比插入元素小或者等于的元素。

  • merge(*iterables, key=None, reverse=False)

将多个排序的输入转换成一个排序后的输出,返回一个排序后的迭代器。和sorted(itertools.chain(*iterables))类似,但是它会返回迭代对象,而不是将数据一次性放入内存。

两个可选参数必须使用成关键字参数。

key指定了如何进行排序,reverse如果是True就会反转。

  • nlargest(n, iterable, key=None)

返回一个迭代器的前n个大的元素列表,key如果提供,指定进行比较的函数。

  • nsmallest(n, iterable, key=None)

对于n比较小的时候比较高效。如果比较大,使用sorted()函数更加高效,当n等于1的时候,使用min和max更高效。如果要重复使用这几个函数,那么考虑将其转换成heap。

基本用法

堆排序可以通过向堆里push元素,然后每次pop出最小的元素来实现

1
2
3
4
5
>>> def heapsort(iterable):
... h = []
... for value in iterable:
... heappush(h, value)
... return [heappop(h) for i in range(len(h))]