python - 什么是 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?

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

Answer 1

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

引用heapq文档：

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

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

您可以在文档的理论部分阅读更多关于数据结构背后的理论。您还可以从 MIT OpenCourseWare Introduction to Algorithms 课程中观看本讲座，该课程对算法进行了一般性的解释。

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

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

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

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

Answer 2

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

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

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

一个堆有三个操作：

1. 查找最小值为 O(1)
2. 插入 O(log n)
3. Remove-Min O(log n)

至关重要的是，插入是 O(log n)，它在排序列表中优于 O(n)。

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

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

道德：如果您使用排序列表编写算法，但只从一端检查和删除，那么您可以通过使用堆使算法更有效。

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

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)

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-max 或 heap-min （导致混淆）指的是最顶层的元素，或者如果是线性的，

堆[0]。是否表示最大值作为开始或最小值作为开始。

我将尽可能不考虑数学。

所以（数字是指数）

heap[0] 有两个孩子。堆[1] 和堆[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] <<< Why is 11 put between 4 and 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 并且更小....规则被打破。堆被重新排序以维持关系。所以它基本上不会看起来是排序的，并且在弹出值之前它看起来不会像之前的迭代一样。

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