如何确定Python的heapq库管理的项目顺序? [英] How is the order of items managed by Python's heapq library determined?

问题描述

给我的印象是，第一个值是确定堆中某个值位置的因素，但事实并非如此.

I was under the impression that the first value was what determined a values position in the heap, however that doesn't seem to be the case.

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)]

推荐答案

heapq上的条件不是所提供列表上的排序保证".而是保证q[k] <= q[2*k+1]和q[k] <= q[2*k+2](在示例中使用q).

The condition on heapq is not a "sort guarantee" over the provided list. Instead, it guarantees q[k] <= q[2*k+1] and q[k] <= q[2*k+2] (using q as in your example).

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

This is due that it is managed internally as a binary tree.

如果仅希望使用排序列表，则可以将heappop用作此处显示.在您的特定示例中，您可以:

If you simply expect to use the sorted list, you can use the heappop as shown here. In your specific example you could:

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

结果如您所料，将是:

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

---

在文档中的此处对此理论进行了解释 .相关的是以下行:

---

The theory is explained here in the docs. Relevant is the following line:

堆的有趣特性是a [0]始终是其最小元素.

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]的直接结果，而条件q[k] <= q[2*k+1]和q[k] <= q[2*k+2]是堆的条件.

Which is a direct result of the condition q[k] <= q[2*k+1] and q[k] <= q[2*k+2], which is a condition of the heap.

但是，对数组其余部分的顺序没有进一步的保证.而且，实际上，以下两个树都是有效的堆:

However, there are no further guarantees about the order on the rest of the array. And, in fact, both following trees are valid heaps:

    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]

这篇关于如何确定Python的heapq库管理的项目顺序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！