Куча (heapq): приоритетная очередь

Структура, которая всегда быстро отдаёт минимум и принимает новые элементы — фундамент Дейкстры и жадных алгоритмов.

Куча (heap) — структура «приоритетная очередь»: даёт минимальный (или максимальный) элемент за O(1), а вставку и извлечение — за O(log n).

Зачем это нужно

Часто нужен не отсортированный массив целиком, а только «самый срочный» элемент прямо сейчас, причём набор постоянно меняется. Сортировать заново после каждого добавления — расточительно. Куча решает это: она держит элементы в частичном порядке, где минимум всегда наверху. На куче строится алгоритм Дейкстры (кратчайшие пути), задачи о k наименьших/больших, слияние отсортированных потоков, симуляции событий по времени. В Python готовая реализация — модуль heapq (минимальная куча на списке).

Идея «на пальцах»

Куча — это двоичное дерево, упакованное в массив, со свойством: родитель не больше своих детей. Поэтому в корне (нулевой элемент массива) всегда минимум. При вставке элемент добавляется в конец и «всплывает» вверх, меняясь с родителем, пока не встанет на место. При извлечении минимума корень заменяется последним элементом, который затем «тонет» вниз. Оба «пути» — высотой log n, отсюда O(log n) на операцию.

Базовые операции heapq

import heapq

h = []
for x in [5, 1, 8, 3, 2]:
    heapq.heappush(h, x)          # вставка за O(log n)

print("Минимум сейчас:", h[0])    # корень — всегда минимум, O(1)

out = []
while h:
    out.append(heapq.heappop(h))  # извлекаем минимум за O(log n)
print("Извлечение по возрастанию:", out)

Главное: h[0] — это всегда текущий минимум (за O(1)), а heappush/heappop сохраняют свойство кучи за O(log n). Последовательное извлечение даёт элементы по возрастанию — это, по сути, сортировка кучей (heapsort) за O(n log n).

Вывод:

Минимум сейчас: 1
Извлечение по возрастанию: [1, 2, 3, 5, 8]

Полезные функции и трюки

heapq умеет больше, чем push/pop. Готовые nsmallest/nlargest находят k крайних элементов, а превратить минимум-кучу в максимум-кучу можно, храня значения с обратным знаком.

import heapq

data = [5, 1, 8, 3, 2, 7, 4]
print("3 наименьших:", heapq.nsmallest(3, data))
print("2 наибольших:", heapq.nlargest(2, data))

# Максимум-куча через отрицание знака:
maxh = []
for x in data:
    heapq.heappush(maxh, -x)
print("Максимум:", -maxh[0])
print("Два наибольших по одному:", -heapq.heappop(maxh), -heapq.heappop(maxh))

# heapify превращает список в кучу на месте за O(n):
arr = [9, 4, 7, 1, 0, 3]
heapq.heapify(arr)
print("Минимум после heapify:", arr[0])

Два важных приёма: отрицание для максимум-кучи (в Python нет встроенной max-heap) и heapify — построение кучи из готового списка за O(n) (быстрее, чем n вставок по O(log n)).

Вывод:

3 наименьших: [1, 2, 3]
2 наибольших: [8, 7]
Максимум: 8
Два наибольших по одному: 8 7
Минимум после heapify: 0

Кортежи: куча с приоритетами

В кучу можно класть кортежи — Python сравнивает их лексикографически (сначала по первому элементу). Это и есть приоритетная очередь: первый элемент кортежа — приоритет, остальное — полезные данные. Именно так устроен Дейкстра: в куче лежат пары (расстояние, вершина).

import heapq

pq = []
heapq.heappush(pq, (2, "задача B"))
heapq.heappush(pq, (1, "задача A"))   # меньший приоритет = раньше
heapq.heappush(pq, (3, "задача C"))
while pq:
    prio, task = heapq.heappop(pq)
    print(f"приоритет {prio}: {task}")

Куча отдаёт задачи в порядке возрастания приоритета. Если приоритеты равны, сравнение пойдёт по второму полю — поэтому туда кладут что-то сравнимое (число), либо уникальный счётчик, чтобы избежать сравнения несравнимых объектов.

Вывод:

приоритет 1: задача A
приоритет 2: задача B
приоритет 3: задача C

Сложность

Подводные камни

• В Python только min-heap. Для максимума отрицай значения (-x) или используй nlargest.
• Нельзя быстро удалить произвольный элемент. Куча умеет убирать только минимум; для «ленивого удаления» в Дейкстре пропускают устаревшие записи.
• Сравнение кортежей. Если в кортеже несравнимые объекты и первые элементы равны — будет ошибка; добавляй уникальный счётчик вторым полем.
• heapify дешевле, чем n отдельных heappush, если все элементы известны заранее.

Итог

• Куча даёт минимум за O(1), вставку и извлечение — за O(log n).
• heapq — минимум-куча; для максимума храни -x; heapify строит кучу за O(n).
• Кортежи (приоритет, данные) превращают кучу в приоритетную очередь — основу Дейкстры.
• Куча не удаляет произвольные элементы; используют ленивое удаление.