使用 heapq 对元组进行排序

Question

我正在使用

heapq

模块对元组列表进行堆排序。

但是，对于第一个元组的键的绑定，heapq 不会自动回退到下一个键：

import heapq
x = [(3, 0, 0), (6, 0, 1), (2, 1, 0), (3, 1, 1)]
heapq.heapify(x)
print(x)

将打印：

[(2, 1, 0), (3, 1, 1), (3, 0, 0), (6, 0, 1)]

我希望

(3, 0, 0)

应该出现在

(3, 1, 1)

之前。我需要指定自定义的比较方法吗？或者我该如何进行这项工作？

Answer 1

正如文档所述，

其最小元素始终是根，heap[0]

但这并不意味着其他元素是有序的。调用

heapify()

后，您会得到

[(2, 1, 0), (3, 1, 1), (3, 0, 0), (6, 0, 1)]

当您删除第一个（最小的）项目时，堆将自行重新排序：

heapq.heappop(x) # returns (2, 1, 0)
print(x)

给予

[(3, 0, 0), (3, 1, 1), (6, 0, 1)]

要获取完整的有序列表，请实现

heapsort()

函数，如示例中所述。

Answer 2

要使用

heapq

模块对元组列表进行排序，您可以实现

heapsort()

函数，如文档的基本示例部分所示：

from heapq import heappop, heappush

def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

x = [(3, 0, 0), (6, 0, 1), (2, 1, 0), (3, 1, 1)]

res = heapsort(x)
print(res)  # -> [(2, 1, 0), (3, 0, 0), (3, 1, 1), (6, 0, 1)]

如您所见，

(3, 0, 0)

将按预期出现在

(3, 1, 1)

之前。

Answer 3

事实证明，当您直接提取堆时，顺序与顺序弹出它们时的顺序不同。虽然当您打印它时，第二个/第三个元素没有排序，但是当您按顺序弹出它们时它们确实已排序：

import heapq
x = [(3, 0, 0), (6, 0, 1), (2, 1, 0), (3, 1, 1)]
heapq.heapify(x)
while x:
    print(heapq.heappop(x))

产生：

(2, 1, 0)
(3, 0, 0) # middle element is 0, comes before 1 in the next
(3, 1, 1)
(6, 0, 1)