什么是Python的heapq模块？

Question

我试过"heapq"，得出的结论是，我的期望值与我在屏幕上看到的不同。我需要有人来解释它是如何工作的，在哪里有用。

从书Python Module of the Week段落2.2排序下写下

If you need to maintain a sorted list as you add and remove values, check out heapq. By using the functions in heapq to add or remove items from a list, you can maintain the sort order of the list with low overhead.

这是我的工作和收获。

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?

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

Answer 1

对堆数据结构的实现存在一些误解。heapq模块实际上是binary heap实现的变体，其中堆元素存储在列表中，如下所述：https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

引用维基百科：

Heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices.

下面的图片将帮助您感受堆的树和列表表示之间的区别，注意，这是一个最大堆，与通常的最小堆相反！）：

一般来说，堆数据结构不同于排序列表，因为它牺牲了关于某个特定元素是否大于或小于任何其他元素的一些信息。堆只能告诉我们，这个元素比它的父元素少，比它的子元素大。数据结构存储的信息越少，修改它所需的时间/内存就越少。比较堆和排序数组之间某些操作的复杂性：

        Heap                  Sorted array
        Average  Worst case   Average   Worst case

Space   O(n)     O(n)         O(n)      O(n)

Search  O(n)     O(n)         O(log n)  O(log n)

Insert  O(1)     O(log n)     O(n)      O(n)

Delete  O(log n) O(log n)     O(n)      O(n)

Answer 2

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

引用^{} documentation：

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].

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

您可以在Theory section of the documentation中阅读更多关于数据结构背后的理论。您还可以观看this lecture from the MIT OpenCourseWare Introduction to Algorithms course，它一般地解释了算法。

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

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

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

如果您只对最小值或第一个n最小值感兴趣，那么您将使用堆，特别是如果您对这些值感兴趣，那么在持续的基础上；添加新项和删除最小值确实非常有效，比每次添加值时重新排序列表更有效。

Answer 3

你的书错了！如您所示，堆不是排序列表（尽管排序列表是堆）。什么是堆？引用斯基纳的算法设计手册

Heaps are a simple and elegant data structure for efficiently supporting the priority queue operations insert and extract-min. They work by maintaining a partial order on the set of elements which is weaker than the sorted order (so it can be efficient to maintain) yet stronger than random order (so the minimum element can be quickly identified).

与排序列表相比，堆遵循较弱的条件：堆不变量。在定义它之前，首先想想为什么放松这种状态可能是有用的。答案是较弱的条件是更容易维护。你可以用堆做得更少，但是你可以更快地做。

堆有三个操作：

1. 查找最小值为O（1）
2. 插入O（日志n）
3. 删除最小O（日志n）

最关键的插入是O（log n），它比排序列表的O（n）强。

什么是堆不变量？”父母支配子女的二叉树。也就是说，“p ≤ c对于p的所有子c”。Skiena用图片演示了在保持不变的情况下插入元素的算法。如果你想一想，你可以自己发明。（提示：它们被称为泡泡上升和泡泡下降）

好消息是，包含电池的Python在heapq模块中为您实现了所有功能。它不定义堆类型（我认为这更容易使用），而是将它们作为列表中的帮助函数提供。

寓意：如果您使用排序列表编写算法，但只检查并从一端删除，则可以使用堆来提高算法的效率。

对于堆数据结构有用的问题，请阅读https://projecteuler.net/problem=500