Python的heapq模块是什么？

Question

我尝试了"heapq"，但得出结论：我的期望与屏幕上看到的不同。我需要有人解释它是如何工作以及在哪些情况下可以有用。

从书籍《Python Module of the Week》第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?

所以，正如你所看到的，“堆”列表根本没有排序，实际上你添加和删除项目的次数越多，它就会变得越混乱。推入的值取不可解释的位置。

这是怎么回事？

- minerals

---

请阅读heapq的理论。 - jfs

如果将这个引用放在错误的上下文中，那么它就是错的。堆不维护有序列表；它维护一个值的集合，使得可以在常数时间内访问或在O(lg n)时间内删除最小的项。你可以通过反复从列表中删除最小的项来检索排序后的列表。 - chepner

在查找引文后，我发现它其实是误导性的。堆并不维护一个已排序的列表，但它确实维护了一个可以用来创建已排序列表的数据结构。该引文遗漏了一个重要细节，即要检索该列表，必须摧毁堆，这是一个关键的细节。 - chepner

l4mpi：我读了官方的Python文档，但还是不明白，你有什么建议吗？:)chepner：这是有误导性的，这就是为什么我提出这个问题。在阅读我提到的书籍后，任何没有额外知识的人都会期望 heapq 维护一个排序列表。 - minerals

没必要这么苛刻；引用明显是错误的，容易让人困惑。对于很多初学者来说，算法理论也可能相当枯燥。 - Martijn Pieters

Answer 1

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

引用自heapq文档：

堆是二叉树，其中每个父节点都小于或等于其任何子节点。此实现使用数组，对于所有k，从零开始计算元素，有heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2]。为了进行比较，将不存在的元素视为无穷大。堆的有趣属性是其最小元素始终是根：heap[0]。

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

您可以在文档中的理论部分了解有关数据结构背后的理论知识。您也可以观看MIT公开课《算法导论》中的讲座，该课程以一般术语解释了该算法。

堆可以非常高效地转换回已排序列表：

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

通过从堆中弹出下一个元素即可找到最小元素。不过，使用sorted(heap)应该更快，因为Python的排序使用的TimSort算法将利用堆中已经存在的部分排序。

如果您只对最小值或前n个最小值感兴趣，特别是如果您一直关注这些值，那么您可以使用堆；添加新项并删除最小项非常高效，比每次添加值时重新排序列表更加高效。

- Martijn Pieters

---

也许我误解了，但是：“之后的两个值将大于或等于第一个值，接下来的四个值将比前三个值大，然后接下来的八个值将更大，以此类推。” 举个反例：[1, 5, 9, 7, 15, 10, 11] 是一个有效的二叉最小堆，但是例如在层次结构中的第三级的 7 仍然比第二级的 9 小。堆中的有序属性仅适用于父子遍历，而不一定适用于“姑婆关系”。 - Daniel Andersson

@DanielAndersson：是的，那句话过于简化了，因此现在基本上是错误的。感谢您指出这一点！ - Martijn Pieters

我认为你的使用方法不太正确， heapsort(range(100, 0 , -1)) 的结果是 100, 1, 2, 3 ... 98, 99。要修复它，请在真正弹出项之前尝试先进行一次堆化操作：``def heapsort(heap):heapq.heapify(heap) return [heapq.heappop(heap) for _ in range(len(heap))] `` - Menglong Li

@AlbertLee: 假设heap是一个合适的堆。 如果您需要首先调用heapify（），那么它就不是一个合适的堆； 您没有更新堆不变量。 - Martijn Pieters

@MartijnPieters，我认为你可以将函数名称更改为generate_sorted_array_from_heap而不是heapysort，你同意吗？ - Menglong Li

@AlbertLee：不，我没有。参数名为 heap，所以函数可以作出这个假设。 - Martijn Pieters

Answer 2

你的书是错的！正如你所展示的，堆不是一个有序列表（虽然有序列表是堆）。那么什么是堆呢？引用Skiena的《算法设计手册》中的话：

堆是一种简单而优雅的数据结构，用于有效地支持优先队列操作insert和extract-min。它们通过在元素集上维护一个部分顺序来工作，该部分顺序比排序顺序要弱（因此可以高效地维护），但比随机顺序要强（因此可以快速识别最小元素）。

与有序列表相比，堆遵循更弱的条件堆不变式。在定义它之前，首先想想放松条件可能会有什么用处。答案是较弱的条件更容易维护。您可以使用堆做更少的事情，但您可以更快地完成它。

堆有三个操作：

1. 查找最小值为O(1)
2. 插入为O(log n)
3. 删除最小值为O(log n)

关键是插入为O(log n)，这打败了有序列表的O(n)。

何谓堆不变式？"父节点支配子节点的二叉树"。也就是说，"p ≤ c对于p的所有子节点c"。Skiena用图片说明了这一点，并继续演示了插入元素时如何保持不变式的算法。如果您认真思考，您可以自己发明它们。（提示：它们被称为bubble up和bubble down）

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

教训：如果您使用有序列表编写算法，但仅从一个端口检查并删除，则可以通过使用堆使算法更有效。

如果需要使用堆数据结构解决问题，请阅读 https://projecteuler.net/problem=500

- Colonel Panic

---

你如何比较哈希表（Python中的字典）和堆表在插入/删除方面的效率？我知道哈希表在最优情况下是O(1)，在最坏情况下是O(n)。堆表的最坏或平均情况下是O(log n)吗？ - enaJ

@enaJ：你不能比较它们：dict（或set）根本不按值排序。 - Davis Herring

Answer 3

有一些对堆数据结构实现的误解。 heapq 模块实际上是二叉堆实现的一个变体，其中堆元素存储在列表中，如此处所述：https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation 引用维基百科：

块引用

堆通常使用数组实现。任何二叉树都可以存储在数组中，但由于二叉堆始终是完全二叉树，因此可以紧凑地存储它。不需要指针空间;相反，可以通过数组索引上的算术来找到每个节点的父级和子级。

下面的图像应该帮助您感受到堆的树形和列表表示之间的差异（请注意，这是最大堆，与通常的最小堆相反！）：

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

        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)

- Alexander Zhukov

Answer 4

我知道这是一个旧问题，但是OP只是错过了答案，附有图表和解释，说明为什么按线性方式列出排序顺序看起来不对。

（因此我不会涉及优化，效率等。我回答的是OP问题的视觉排序结构）

他在pymotw.com上，但如果他只到达： https://pymotw.com/2/heapq/ “最小堆要求父节点小于或等于其子节点”

所以想象一下树和金字塔。

这也不是一个坏链接 https://medium.com/basecs/learning-to-love-heaps-cef2b273a238 因此，每个父级都有两个子级策略。孩子们也只能有两个子元素。

它的美妙之处在于孩子们将始终小于或等于（堆最大）他们的父母，或者大于或等于（堆最小）他们的父母。

heap-max或heap-min（这会引起混淆）是指最顶部的元素，或者如果是线性的，则是heap [0]。无论它表示最大值还是最小值作为开始。

我将尽可能地省略数学内容。

所以（数字是索引）

heap [0]有两个孩子。 heap [1]和heap [2]。

heap [1]的孩子将是heap [3]和heap [4]

heap [2]的孩子将是heap [5]和heap [6]

heap [3]的孩子将是heap [7]和heap [8]

heap [4]的孩子将是heap [9]和heap [10]

等等。

所以，问题是，

[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<<为什么11被放在4和6之间？

因为值11存储在索引5处。索引5是索引2的子级，其值为3。值4（索引4）是索引1的子级。

它是按最小顺序排序的，只是在线性方式下检查时看起来不是这样。

parent -> child 

[0] -> [0] is 2
-
[0] -> [1] is 3
[0] -> [2] is 5
-
[1] -> [3] is 7
[1] -> [4] is 4
[2] -> [5] is 11  <-- between 4 and 6
[2] -> [6] is 6

所以...又是这样。而且这是真的。 “最小堆要求父节点小于或等于其子节点” 让自己疯狂，对于最大堆也是如此。 （你有没有写过这些东西，然后等着被某个博士后压扁？） 所以让我们弹出第一个元素，并像正常的列表或队列一样处理。

[0] -> [0] is 3
-
[0] -> [1] is 5
[0] -> [2] is 7
-
[1] -> [3] is 4
[1] -> [4] is 11  

让我们停下来。

索引1的值为5。索引3的子值为4，比它小……规则被打破了。堆被重新排序以维护关系。因此，它基本上永远不会看起来已排序，并且在弹出值之前与先前的迭代完全不同。

有方法可以重新排序节点，第二篇文章讨论了它们。我只是想具体回答这个问题。

- IGotAHeadache