Куча — это структура данных, которая позволяет получать элемент с минимальным или максимальным значением. В Python для работы с кучей есть встроенный модуль heapq. В этом модуле реализована минимальная куча: элемент с минимальной характеристикой находится всегда в начале списка на позиции с индексом \(0\). heapq не создаёт отдельный тип «куча», а работает со списками, реализуя свойства кучи при добавлении и удалении элементов.

 

Пример \(1\)

 

 

Обрати внимание на функцию heapq.heappush, которая добавляет элементы в кучу, а также на то, что весь список не отсортирован, но минимальный элемент находится на месте с нулевым индексом.

 

Для извлечения из кучи используется функция heapq.heappop. Она извлекает и возвращает элемент из кучи, удаляя его из списка и восстанавливая свойства кучи.

 

Пример \(2\)

 

В этом случае в качестве данных мы используем кортеж — пару значений, в нашем примере это будет пара «приоритет — задача».

 

 

Здесь мы используем вывод в цикле while до тех пор, пока не опустеет список. Так видно, что после удаления наименьшего элемента свойства кучи восстанавливаются.