Очередь с приоритетом – это такая коллекция, которая поддерживает обязательно две следующие операции: вставка элемента с некоторым приоритетом (это может быть число или другой сравнимый объект) и извлечение элемента с наибольшим (или наименьшим приоритетом).

Очередь с приоритетом эффективно реализовать с помощью кучи. Двоичная куча – бинарное дерево, где значение в любой вершине не меньше (больше), чем значения её потомков, при этом заполнение уровней должно быть последовательным (без дырок и перескоков на следующий уровень, если текущий уровень не закончен). Работа с кучей осуществляется за время порядка O(log n). А построение кучи из массива – за O(n), где n – число элементов.

Кучу удобно хранить в массивах. Напомню, что списки (list) в Python – это и есть массивы переменной длины, а не связные списки (linked list), как в других языках. Поэтому доступ к элементу по индексу осуществляется за O(1). Пускай в корень дерева мы положим наименьший элемент, а корнем дерева будет нулевой элемент списка heap[0]. Его потомками будут элементы heap[1] и heap[2]. В общем виде потомками элемента heap[k] будут heap[2*k+1] и heap[2*k+2]. Такая индексация позволяет хранить в массиве двоичное дерево компактно и удобно получать доступ к его элементам. По условиям кучи должны соблюдаться условия heap[k] <= heap[2*k+1] и heap[k] <= heap[2*k+2].

В Python есть модуль heapq, который предоставляет процедурный интерфейс по работе с двоичными кучами, причем его функции принимают в качестве кучи именно обычные объекты типа list. 

Создать кучу можно двумя способами: 

1. начать с пустого списка [] и заполнить его методом heappush 
2. взять существующий список и превратить его в кучу на месте (in-place) функцией heapify. heapify не возвращает новый список, а модифицирует переданный:

Основные функции:

▶ heappush(heap, item) – добавляет в кучу элемент item.

▶ heappop(heap) — возвращает наименьший элемент и удаляет его из кучи. Если не надо удалять, то просто heap[0].

▶ heappushpop(heap, item) – добавляет в кучу item, а после возвращает наименьший элемент (работает немного быстрее, чем в две операции).

▶ heapreplace(heap, item) – возвращает наименьший элемент, а потом уже добавляет новый item (работает немного быстрее, чем в две операции).

^ℹ️ Помните! Отсортированный список является кучей – это легко проверить по условиям. Поэтому если ваш массив заранее отсортирован, то не надо вызывать heapq.heapify. 

^ℹ️ Но не любая куча – отсортированный список. Построение из массива – кучи, а из кучи – отсортированного массива – это сортировка кучей: мы наполняем последовательно кучу, а потом по порядку извлекаем наименьшие элементы, пока куча не истощится:

В примерах выше, мы пользовались числами, как элементами кучи, потому что числа легко сравнимы. В реальной жизни мы оперируем произвольными объектами с их приоритетами. Для перехода от кучи к очереди с приоритетами можно использовать следующий трюк: использовать как элементы кортежи вида (приоритет, объект) или (приоритет, идентификатор, объект), если объекты несравнимы. Приоритет – число (например: важность задачи или время запуска какого-либо процесса). Идентификатором может служить порядковый номер.

Куча возвращает минимальный элемент (heappop), а кортежи сравниваются поэлементно слева направо. Сначала идет -priotiry. Знак минус, чтобы сначала возвращался не минимальный приоритет, а максимальный. Если приоритеты равны, то будет возвращен элемент с наименьшим идентификатором ident, т.е. тот, что был добавлен раньше всех для данного значения приоритета.