奇怪的Python heap: heappop() 第一次输出

Question

第一个 heappop() 不是数组的最小值，而是第一个索引。

之后，heappop() 开始工作

我想也许是heappop()之后的自动heapify()？检查文件但一无所获

>>> a = [412,23,24,24,32,5,324,12,41,125,5,32,41,24,12,5,34,1]
>>> heappop(a)
412
>>> heappop(a)
1
>>> heappop(a)
23
>>> a
[24, 24, 5, 12, 32, 32, 324, 5, 41, 125, 5, 34, 41, 24, 12]

顺便说一句，如果您一开始使用 heapify() a，那么 heappop() 运行良好。如果对此有任何解释，将不胜感激。谢谢！

>>> a = [412,23,24,24,32,5,324,12,41,125,5,32,41,24,12,5,34,1]
>>> heapify(a)
>>> a
[1, 5, 5, 5, 32, 24, 12, 12, 24, 125, 412, 32, 41, 24, 324, 23, 34, 41]
>>> heappop(a)
1
>>> heappop(a)
5
>>> heappop(a)
5
>>> heappop(a)
5
>>> heappop(a)
12

Answer 1

documentation 说：

To create a heap, use a list initialized to [], or you can transform a populated list into a heap via function heapify().

由于您没有在第一个代码块中执行此操作，因此您的列表不是堆。

heappush、heappop、heappushpop、heapreplace保持堆不变性等函数。但这意味着在调用之前，列表应该是一个堆。只有这样才能保证调用后list仍然是堆

这些方法具有 O(logn) 时间复杂度，因此它们不可能从任何随机列表中生成堆。 heapify 的时间复杂度为 O(n)。堆的强大之处在于，一旦你建立了它，你就可以利用有效的方法来处理它，而不必再次调用更昂贵的heapify。

奇怪的Python heap: heappop() 第一次输出

Weird Python heap: heappop() output at the first time

python

heap

heapq