Heapq в Python3 не работает с кортежами, поскольку он не соответствует порядку ожидания

Question

Все говорят, что если вы введете кортеж в heapq, в качестве коэффициента сравнения будет принят первый аргумент.

Но это не так! Мне интересно, что не так в моем коде?

for task_name, counter in tasks_counter.items():
    heappush(tasks_q, (-int(counter), task_name, counter))
heapify(tasks_q)
while tasks_q:
    print(tasks_q.pop())

выход

(-1, 'G', 1)
(-1, 'F', 1)
(-1, 'E', 1)
(-1, 'D', 1)
(-1, 'C', 1)
(-1, 'B', 1)
(-6, 'A', 6)

Я думаю, что сначала я должен получить предмет со значением A, верно? Но это не так.

Есть ли альтернативное решение для использования встроенной очереди приоритетов с Python?

Вывод другого примера.

Answer 1

Вы используете функцию pop из list. Вам нужно использовать функцию heapq.heappop. Он будет корректировать список для поддержания инварианта кучи по пути. См. Основные примеры .

Также нет необходимости вызывать heapify, если вы начинаете с [] и повторно вызываете heappush. heappush уже обеспечивает сохранение инварианта кучи.