什么是Python的heapq模块？

小编典典

什么是Python的heapq模块？

python

我尝试了“
heapq”，得出的结论是我的期望与我在屏幕上看到的有所不同。我需要有人解释它是如何工作的以及在什么地方有用。

从书的周Python模块根据第
2.2排序 它被写入

如果在添加和删除值时需要维护排序列表，请查看heapq。通过使用heapq中的函数在列表中添加或删除项目，您可以以较低的开销维护列表的排序顺序。

这就是我要做和得到的。

import heapq
heap = []

for i in range(10):
    heap.append(i)

heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

heapq.heapify(heap)    
heapq.heappush(heap, 10)    
heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

heapq.heappop(heap)
0    
heap
[1, 3, 2, 7, 4, 5, 6, 10, 8, 9] <<< Why the list does not remain sorted?

heapq.heappushpop(heap, 11)
1
heap
[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6?

因此，正如您所看到的，“堆”列表根本没有排序，实际上，您添加和删除的项目越多，它就越混乱。推入的值占据无法解释的位置。到底是怎么回事？

阅读 218

2021-01-20

共1个答案

小编典典

该heapq模块维护 堆不变式 ，这与按排序顺序维护实际列表对象不同。

引用heapq文档：

堆是二叉树，其每个父节点的值都小于或等于其任何子节点。此实现使用了该阵列heap[k] <= heap[2*k+1]及heap[k] <= heap[2*k+2]所有k，计数从零元素。为了进行比较，不存在的元素被认为是无限的。堆的有趣特性是它的最小元素始终是根heap[0]。

这意味着查找最小的元素（只需take
heap[0]）非常有效，这对于优先级队列非常有用。之后，接下来的2个值将大于（或等于）第一个，之后的下一个4将比其“父”节点大，然后接下来的8个更大，依此类推。

您可以在文档的“理论”部分中详细了解数据结构背后的理论。您也可以在MIT
OpenCourseWare算法入门课程中观看此讲座，该课程以一般术语解释该算法。

可以非常有效地将堆转换为排序列表：

def heapsort(heap):
    return [heapq.heappop(heap) for _ in range(len(heap))]

通过仅从堆中弹出下一个元素。sorted(heap)但是，使用应该会更快，因为Python排序所使用的TimSort算法将利用堆中已经存在的部分排序。

如果您只对最小值或前几个最小值感兴趣，则可以使用堆n，尤其是如果您对连续不断地对这些值感兴趣的话；实际上，添加新项目并删除最小的项目确实非常有效，这比每次添加值时都诉诸列表更为有效。

2021-01-20