Python 的 heapq 模块是什么？

我尝试了 “堆”，得出的结论是，我的期望与我在屏幕上看到的不同。我需要有人解释一下它是怎么工作的，在哪里能派上用场。

从书 每周 Python 模块下段 2.2分类它是写

如果在添加和删除值时需要维护排序列表, 通过使用 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?

因此，正如您所看到的，“堆”列表根本没有排序，实际上，添加和删除的项目越多，它就变得越混乱。被推动的价值观采取无法解释的立场。 发生什么事了？

78801 次浏览
小开
最佳答案

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

引自 heapq文档:

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

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

您可以在 文献理论部分中阅读更多关于数据结构背后的理论。您还可以查看 这是 MIT开放课程算法入门课程的讲座，它对算法进行了一般性的解释。

可以非常有效地将堆转换回排序列表:

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

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

如果你只对最小值或者第一个 n的最小值感兴趣，你会使用堆，特别是如果你一直对这些值感兴趣的话; 添加新的项目和删除最小的项目确实是非常有效的，比每次添加一个值的时候重新使用列表更有效。

小开

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

引用维基百科:

堆通常用数组实现。任何二进制树都可以存储在数组中，但是因为二进制堆始终是一个完整的二进制树，所以它可以被紧凑地存储。指针不需要空间; 相反，每个节点的父节点和子节点可以通过对数组索引进行运算来找到。

下面的图片可以帮助您感受堆和(注意，这是一个最大堆，与通常的最小堆相反！)的树和列表表示形式之间的差异:

enter image description here

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

        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)
小开

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

堆是一种简单而优雅的数据结构，可以有效地支持优先级队列操作的插入和提取-min。它们的工作原理是在元素集合上维持一个偏序，这个偏序比排序顺序弱(因此可以有效地维护) ，但比随机顺序强(因此可以快速识别最小元素)。

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

堆有三个操作:

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

至关重要的是，Insert 是 O (log n) ，对于排序的列表，它优于 O (n)。

堆不变量是什么？“父母支配孩子的二叉树”。也就是“ p ≤ c代表所有子代 c of p”。Skiena 用图片进行了说明，并继续演示了在保持不变量的同时插入元素的算法。如果你想一想，你可以自己发明它们。(提示: 它们被称为泡沫上升和泡沫下降)

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

寓意: 如果您使用排序列表编写算法，但只从一端进行检查和删除，那么可以使用堆来提高算法的效率。

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

小开

我知道这是一个较老的问题，但 OP 只是错过了答案，带有图表和解释为什么排序顺序在以线性方式列出时看起来不对劲。

(所以我不打算进入优化，效率，等等。我在回答 OP 问题的视觉顺序和结构)

他在 pymotw.com 上，但是如果他能看到: Https://pymotw.com/2/heapq/

“最小堆要求父堆小于或等于其子堆”

想想树，想想金字塔。

这个链接也不错 Https://medium.com/basecs/learning-to-love-heaps-cef2b273a238

所以每个父母都有一个二胎政策，而孩子也只能有两个子元素。

它的美妙之处在于，孩子们要么总是小于或等于他们的父母(堆最大值) ，要么总是大于或等于他们的父母(堆最小值)。

Top-most 元素或者如果是线性的，那么堆-max 或者堆-min (这会导致混淆)指的是最顶层的元素,

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

我会尽可能把数学省略掉。

所以(数字就是指数)

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

孩子们会变得越来越多

孩子们会变得越来越多

孩子们会变得越来越多

孩子们会变得越来越多

诸如此类。

那么，问题是,

[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，并且更小... 。规则被打破了。对堆进行重新排序以维护关系。所以它基本上，从来没有 听着排序，它看起来也不会像它自己的前一次迭代那样，在弹出值之前。

有一些重新排序节点的方法，第二篇文章讨论了这些方法。我只是想明确地回答这个问题。


提交答案