В Python, как я должен реализовать минимальную кучу в списке кортежей?

Question

Я пытаюсь реализовать минимальную кучу в списке кортежей. Например:

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

как я могу накапливать A на основе второго элемента этого кортежа, чтобы A был накапливаться до [('b',1),('a',2)]? (Я должен поддерживать минимальную кучу.)

Answer 1

Согласно комментарию @ JimMischel, поместите свои кортежи в кортеж с приоритетом в качестве первого элемента.Затем используйте 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)