Очередь с приоритетами - это структура данных, которая поддерживает две операции: добавление элемента и извлечение минимального элемента среди всех ранее добавленных.

Одна из самых распространённых реализаций очереди с приоритетами - бинарная куча (binary heap). Это полное бинарное дерево, обладающее следующим свойством: ключ, хранящийся в каждом узле, меньше или равен (≤) ключам в дочерних узлах.
Минимальный элемент из всех находится в корне дерева.

             1

      3               7

  5       4       9       8

15 16   17 18   19

В бинарной куче операции вставки и извлечения минимального элемента выполняются за O(log n).


Хранение бинарной кучи в памяти

Полное бинарное дерево обычно хранится в массиве, где:

* левый потомок элемента x[i] находится по индексу 2*i + 1,
* правый потомок - по индексу 2*i + 2.

Пример массива для дерева выше:

[1, 3, 7, 5, 4, 9, 8, 15, 16, 17, 18, 19]

Работа с кучей в Python

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

Пример использования:

from heapq import *

# Создаём список
heap = [3, 2, 1]

# Преобразуем список в кучу
heapify(heap)
print(heap)  # [1, 2, 3]

# Добавляем элемент в кучу
heappush(heap, 0)
print(heap)  # [0, 1, 3, 2]

# Извлекаем минимальный элемент
print(heappop(heap))  # 0

# Куча после извлечения
print(heap)  # [1, 2, 3]

👉@BookPython