Алгоритм heapq в Python работает следующим образом: модуль берёт список элементов и перестраивает его таким образом, чтобы элементы соответствовали критериям минимальной кучи (min-heap). 2

В min-куче для любого данного узла I значение I меньше или равно значениям его детей. 4 Таким образом, наименьший элемент всегда находится в корне. 4

Чтобы поместить элемент в кучу, Python сначала выбирает, куда его вставить. 3 Если нижний слой заполнен не до конца, узел добавляется в следующий открытый слот. 3 Иначе создаётся новый уровень и элемент добавляется в него. 3

Как только узел добавлен, Python сравнивает новый узел с его родителем. 3 Если свойство кучи нарушено, узел и родительский объект обмениваются местами. 3 Проверка продолжается до тех пор, пока не будет восстановлено свойство кучи или не будет достигнут корень. 3

Чтобы вытолкнуть наименьший элемент при сохранении свойства кучи, используется функция heappop(). 3 После этой операции куча автоматически настраивается, и следующий наименьший элемент занимает позицию корня. 4