0

第一个 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
4

1 回答 1

2

文档说:

要创建堆,请使用初始化为 的列表[],或者您可以通过函数将填充列表转换为堆heapify()

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

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

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

于 2021-09-24T06:33:49.207 回答