在python中，我应该如何在元组列表上实现最小堆？

Question

我正在尝试在元组列表上实现一个最小堆。例如：

A=[('a',2),('b',1)]

我如何根据这些元组的第二个元素堆积A，以便A将堆积为[('b',1),('a',2)]？(我必须维护一个最小堆。)

Answer 1

根据@JimMischel的评论，将您的元组放在一个tuple中，并将优先级作为第一个元素。然后使用heapq

import heapq

list = [('a', 2), ('b', 1), ('c', 0), ('d', 1)]
heap_elts = [(item[1], item) for item in list]
heapq.heapify(heap_elts)  # you specifically asked about heapify, here it is!
while len(heap_elts) > 0:
    print(heapq.heappop(heap_elts)[1])    # element 1 is the original tuple

产生：

('c', 0)
('b', 1)
('d', 1)
('a', 2)

Answer 2

import heapq

A=[('a',2),('b',1), ('d', 0), ('c', 2), ('a', 2)]
h = []
for el in A:
    heapq.heappush(h, (el[1], el[0]))

print(h)

​

结果：

[(0, 'd'), (2, 'a'), (1, 'b'), (2, 'c'), (2, 'a')]