使用 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

如文档所述，

its smallest element is always the root, 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)]

要获得完整的有序列表，请按照 examples.

中所述实施 heapsort() 函数

Answer 2

要使用 heapq 模块对元组列表进行排序，您可以实现 heapsort() 函数，如文档的 Basic Examples 部分所示：

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) 之前。

使用 heapq 对元组进行排序

Sorting tuples with heapq

python

heapsort

python-3.x