在现实生活中你会如何使用heapq模块？
在看了Guido的用Python在2MB内存中排序一百万个32位整数这篇文章后，我发现了heapq模块，但这个概念对我来说有点抽象。
其中一个原因是我对堆的概念还不太理解，不过我明白Guido是怎么用它的。
除了他那个有点疯狂的例子之外，你会用heapq模块来做什么呢？
它一定要和排序或最小值有关吗？是因为它比其他方法快才用的吗？还是说它能做一些优雅的事情，而这些事情用其他方法做不到？
3 个回答
3
我偶然发现了这个事情，是因为我想看看怎么在Python 2.6中实现计数器模块。你可以看看collections.Counter的实现和用法。其实这个功能是通过heapq来实现的。
6
把堆和自平衡二叉树相比，如果只看复杂度，堆似乎没有太多优势：
- 插入数据：两者都是 O(logN)
- 删除最大元素：两者也是 O(logN)
- 从一个元素数组构建结构：堆是 O(N)，而二叉树是 O(N log N)。
不过，自平衡二叉树通常需要每个节点指向它的子节点，这样才能高效工作，而堆则是把数据紧凑地存储在一个数组里。这种方式可以在固定的内存中存储更多的数据。
所以在只需要插入和删除最大值的情况下，堆是非常合适的，通常能用一半的内存来实现自平衡二叉树（而且如果需要实现起来也简单得多）。堆的标准用法就是优先队列。
20
你会在事件调度器中看到优先队列，这些调度器不断添加新事件，并需要使用堆来高效地找到下一个安排的事件。一些例子包括：
- Python自带的sched模块: http://hg.python.org/cpython/file/2.7/Lib/sched.py#l106
- Tornado网络服务器: https://github.com/tornadoweb/tornado/blob/da78384/tornado/ioloop.py#L260
- Twisted互联网服务器: http://twistedmatrix.com/trac/browser/trunk/twisted/internet/base.py#L712
heapq的文档中包含了优先队列实现的说明，这些说明涵盖了常见的使用场景。
此外，堆也非常适合用于实现部分排序。例如，heapq.nsmallest和heapq.nlargest在内存使用上会更加高效，并且进行的比较次数也比完全排序后再切片要少得多：
>>> from heapq import nlargest
>>> from random import random
>>> nlargest(5, (random() for i in xrange(1000000)))
[0.9999995650034837, 0.9999985756262746, 0.9999971934450994, 0.9999960394998497, 0.9999949126363714]