python - Python的heapq库管理的项目的顺序是如何确定的？

Question

我的印象是第一个值决定了堆中的值位置，但事实似乎并非如此。

from __future__ import print_function
import heapq

q = []
heapq.heappush(q, (10, 11))
heapq.heappush(q, (11, 12))
heapq.heappush(q, (9, 10))
print(q)

这给了我一个输出

[(9, 10), (11, 12), (10, 11)]

但是我期待这样的输出

[(9, 10), (10, 11), (11, 12)]

Answer 1

heapq 的条件不是对所提供列表的“排序保证”。相反，它保证 q[k] <= q[2*k+1]和q[k] <= q[2*k+2] (在您的示例中使用 q )。

这是因为它在内部作为二叉树进行管理。

如果您只是希望使用排序列表，则可以使用 heappop如shown here 。在您的具体示例中，您可以:

sorted_q = [heappop(q) for i in range(len(q))

结果如您所料，将是:

>>> print sorted_q
[(9, 10), (10, 11), (11, 12)]

<小时/>

理论解释here in the docs 。相关的是以下行:

The interesting property of a heap is that a[0] is always its smallest element.

这是条件 q[k] <= q[2*k+1] 的直接结果和q[k] <= q[2*k+2] ，这是堆的一个条件。

但是，对于数组其余部分的顺序没有进一步的保证。事实上，以下两棵树都是有效的堆:

    0
 1     2
2 5   3 4

和

    0
 2     1
5 3   4 2

分别存储为

[0, 1, 2, 2, 5, 3, 4]

和

[0, 2, 1, 5, 3, 4, 2]