什么是Python的heapq模块？

Question

我尝试了"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?

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

Answer 1

该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最小值感兴趣,则使用堆,特别是如果您持续对这些值感兴趣; 添加新项目并删除最小项目确实非常有效,比每次添加值时使用列表更有效.

Answer 2

你的书错了!如您所示,堆不是排序列表(尽管排序列表是堆).什么是堆？引用Skiena的算法设计手册

堆是一种简单而优雅的数据结构,用于有效支持优先级队列操作insert和extract-min.它们通过维持元素集合的部分顺序来工作,这些元素集合比排序顺序弱(因此它可以有效地维护)但比随机顺序更强(因此可以快速识别最小元素).

与排序列表相比,堆遵循堆不变的较弱条件.在定义之前,首先要考虑为什么放松这种情况可能会有用.答案是较弱的条件更容易维护.你可以用堆做得少,但你可以更快地做到.

堆有三个操作:

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

Crucially Insert是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)