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

When you remove the first (smallest) item, the heap will reorder myself:

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

Gives

[(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)