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

从第2.2 节中的本周Python模块一书中可以看出它的排序

如果在添加和删除值时需要维护排序列表，请查看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?

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

解决方案

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

引用heapq文档：

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

这意味着找到最小元素（只需要heap[0]）非常有效，这对于优先级队列来说非常有用。之后，接下来的2个值将比第1个更大（或相等），之后的4个将大于它们的“父”节点，然后接下来的8个更大，等等。

您可以在文档的Theory部分中阅读有关数据结构背后的理论的更多信息。您还可以从麻省理工学院开放式课件的算法入门课程中观看本课程，该课程以一般术语解释算法。

堆可以非常有效地转回到排序列表中：

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

只需从堆中弹出下一个元素即可。sorted(heap)然而，使用应该更快，因为Python的排序使用的TimSort算法将利用堆中已经存在的部分排序。

如果您只对最小值或第一个n最小值感兴趣，则使用堆，特别是如果您持续对这些值感兴趣; 添加新项目并删除最小项目确实非常有效，比每次添加值时使用列表更有效。