你会在现实生活中使用heapq Python模块吗？

Question

在阅读Guido 使用Python在2MB内存中对一百万个32位整数进行排序后,我发现了该heapq模块,但这个概念对我来说非常抽象.

一个原因是我完全不理解堆的概念,但我确实理解Guido如何使用它.

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

它必须始终与排序或最小值相关吗？它只是你使用的东西,因为它比其他方法更快？或者你可以做一些你不能没有的优雅事物吗？

Answer 1

该heapq模块通常用来实现优先级队列.

您会在事件调度程序中看到不断添加新事件的优先级队列,并且需要使用堆来有效地定位下一个调度事件.一些例子包括:

• Python自己的sched模块:http: //hg.python.org/cpython/file/2.7/Lib/sched.py#l106
• 在龙卷风 Web服务器: https://github.com/facebook/tornado/blob/master/tornado/ioloop.py#L260
• 扭曲的互联网服务器: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]

Answer 2

将它与自平衡二叉树进行比较,如果只看复杂性,堆似乎不会带来太多收益:

• 插入:两者都是O(logN)
• 删除最大元素:O(logN)
• 从堆的元素数组O(N)构建结构,为二叉树构建O(N log N).

但是,虽然二叉树往往需要每个节点指向其子节点以提高效率,但是堆将其数据紧密地存储到数组中.这允许您在固定数量的内存中存储更多数据.

因此,对于情况下,当你只需要插入和max-拔除,堆是完美的,可以经常使用一半的内存作为自我平衡二叉树(和实施容易得多,如果你有).标准用例是优先级队列.