python - 在现实生活中，您会使用 heapq Python 模块做什么？

Question

读完 Guido 的 Sorting a million 32-bit integers in 2MB of RAM using Python ，我发现了 heapq 模块，但这个概念对我来说非常抽象。

一个原因是我没有完全理解堆的概念，但我确实理解 Guido 是如何使用它的。

现在，除了他有点疯狂的例子，你会用 heapq 模块做什么？

它必须始终与排序或最小值相关吗？它只是你使用的东西，因为它比其他方法更快吗？或者你能做一些你离不开的非常优雅的事情吗？

Answer 1

heapq module通常用于实现 priority queues .

您会在事件调度器中看到优先级队列，它们不断添加新事件并且需要使用堆来有效地定位下一个调度事件。一些示例包括:

• Python 自己的 sched模块:http://hg.python.org/cpython/file/2.7/Lib/sched.py#l106
• Tornado网络服务器:https://github.com/facebook/tornado/blob/master/tornado/ioloop.py#L260
• Twisted互联网服务器:http://twistedmatrix.com/trac/browser/trunk/twisted/internet/base.py#L712

heapq 文档包括 priority queue implementation notes它解决了常见的用例。

此外，堆非常适合实现部分排序。例如， 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]