Приоритетная очередь (куча)

Куча, которая всегда знает, где лучшее — и обновляется за log n

Представь приёмный покой в больнице. Пациенты приходят в случайном порядке, но лечить нужно сначала самых тяжёлых. Как врачу быстро находить «самого срочного» — особенно когда список большой и меняется каждую минуту?

Искать максимум в массиве каждый раз. Для тысячи пациентов — тысяча сравнений на каждое «кого лечить?». Для миллиона — миллион. Каждое действие в одиночку быстрое, но суммарно всё ужасно медленно.

Держать массив отсортированным. Максимум найти легко (он в конце), но вставка нового пациента — сдвиг половины массива. Снова линейное время.

Куча (heap, priority queue) — структура данных, которая умеет ровно три вещи:

Куча — это бинарное дерево с одним простым правилом:

Обрати внимание: между братьями (левым и правым ребёнком) никаких отношений нет. Левый может быть больше правого, меньше или равен — куче всё равно. Важно только, чтобы каждый ребёнок был не больше своего родителя.

Дерево заполняется по уровням слева направо, без дыр. Это называется полное бинарное дерево. Именно благодаря этому высота дерева всегда ≈ log₂(n), и операции такие быстрые.

Самый неожиданный факт: никакое «настоящее дерево» с указателями и ссылками не создаётся. Куча живёт в обычном массиве. Индексы связаны простыми формулами:

# Нумерация с 0 (так и в Python, и в C++)
parent(i) = (i - 1) // 2
left(i)   = 2*i + 1
right(i)  = 2*i + 2

У корня (i = 0) родителя нет. У листьев (элементов с большим индексом) детей нет — формулы вернут индексы за пределами массива.

Как куча сохраняет своё правило, когда мы добавляем или удаляем элементы? Вся магия — в двух процедурах: всплытие (sift up) и погружение (sift down).

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

Максимум — это всегда корень. Мы его забираем. Но дерево не может остаться без корня, поэтому на его место ставим последний элемент (бывший самый дальний лист). Скорее всего, он нарушает правило. Тогда сравниваем его с детьми, меняем с бóльшим из них, и так «тонем» вниз, пока не встанем на место.

Обрати внимание, что снизу одновременно показан массив. Дерево и массив — это одно и то же: корень лежит в [0], его дети в [1] и [2], и так далее.

Полное бинарное дерево на n вершинах имеет высоту ≈ log₂(n). Всплытие и погружение — это пути по высоте: каждый шаг либо вверх к родителю, либо вниз к одному из детей. Значит, и то, и другое — не более log n сравнений.

Для сравнения: поиск максимума в несортированном массиве на миллион элементов — это миллион сравнений. Куча быстрее в 50 000 раз.

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

import heapq

pq = []                     # обычный список
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)

pq[0]                       # 2 — верх (min-heap!)
heapq.heappop(pq)           # вернёт 2 и удалит

# Из готового списка — O(n)
data = [5, 2, 8, 1, 9]
heapq.heapify(data)         # data стал min-heap-ом

#include <queue>
#include <vector>

priority_queue<int> pq;        // max-heap по умолчанию
pq.push(5); pq.push(2); pq.push(8);

pq.top();                      // 8 — верх (max-heap!)
pq.pop();                      // удалить 8

// min-heap — через greater
priority_queue<int,
    vector<int>,
    greater<int>> pq2;

// Построить кучу из готового вектора — O(n)
vector<int> data = {5, 2, 8, 1, 9};
priority_queue<int> pq3(data.begin(), data.end());

Часто в куче хранится и приоритет, и «полезная нагрузка» (имя, ID, что угодно). Пары сравниваются поэлементно: сначала по первому полю, при равенстве — по второму.

pq = []
heapq.heappush(pq, (3, "Иван"))
heapq.heappush(pq, (7, "Маша"))
heapq.heappush(pq, (1, "Пётр"))

heapq.heappop(pq)           # (1, 'Пётр')
heapq.heappop(pq)           # (3, 'Иван')

// min-heap из пар (приоритет, имя)
priority_queue<
    pair<int, string>,
    vector<pair<int, string>>,
    greater<>
> pq;

pq.push({3, "Иван"});
pq.push({7, "Маша"});
pq.push({1, "Пётр"});

pq.top();                   // {1, "Пётр"}
pq.pop();
pq.top();                   // {3, "Иван"}

Самое красивое применение кучи — жадные алгоритмы. Это такие алгоритмы, где решение строится по шагам, и на каждом шаге мы берём локально лучший элемент (максимум, минимум — смотря по задаче). Если на каждом шаге нужно находить лучший среди оставшихся, куча даёт это за log n.

Условие. У тебя n верёвок разной длины. За одно действие можно связать две верёвки — получится одна длиной a + b. Стоимость связывания равна длине получившейся верёвки. Надо связать все верёвки в одну и минимизировать суммарную стоимость всех связываний.

Идея. Каждая верёвка, которую мы связываем рано, будет «участвовать» в длине всех следующих связываний — её длина добавится к сумме много раз. Поэтому длинные верёвки хочется связывать в последнюю очередь, а короткие — в первую. Жадный шаг: всегда бери две самые короткие. Для этого идеально подходит min-heap: за O(log n) — найти пару минимумов, за O(log n) — вернуть новую длину обратно в очередь.

import heapq

def min_cost(ropes):
    heapq.heapify(ropes)                 # превратить в min-heap за O(n)
    total = 0
    while len(ropes) > 1:
        a = heapq.heappop(ropes)         # самая короткая
        b = heapq.heappop(ropes)         # вторая самая короткая
        cost = a + b
        total += cost
        heapq.heappush(ropes, cost)      # вернуть связку обратно
    return total

min_cost([4, 3, 2, 6])                   # → 29

#include <queue>
#include <vector>

long long min_cost(vector<int> ropes) {
    // min-heap, сразу построенный из вектора — O(n)
    priority_queue<int, vector<int>, greater<int>> pq(
        ropes.begin(), ropes.end()
    );
    long long total = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();     // самая короткая
        int b = pq.top(); pq.pop();     // вторая самая короткая
        int cost = a + b;
        total += cost;
        pq.push(cost);                  // вернуть связку обратно
    }
    return total;
}

min_cost({4, 3, 2, 6});                 // → 29

Без кучи пришлось бы на каждом шаге заново искать два минимума — это O(n²). С кучей — O(n log n). Для n = 100 000 это разница между мгновенно и считай до утра.

Есть k уже отсортированных списков общей длиной N. Чтобы слить их в один отсортированный, кладём в min-heap по одному элементу с начала каждого списка. Достаём минимум, добавляем в результат, кладём в кучу следующий элемент из того же списка. Итого O(N log k) — быстрее, чем O(N log N) от обычной сортировки.

Поиск кратчайших путей в графе. На каждом шаге мы берём вершину с минимальным текущим расстоянием и обновляем её соседей. Без кучи — O(n²). С min-heap — O((n + m) log n).

Из огромного потока данных найти k самых больших. Держим min-heap размера k. Новый элемент сравниваем с верхом кучи: если больше — меняем. Память всего O(k), не O(n). Работает, даже когда все данные в память не помещаются.

Моделирование работы светофоров, аэропорта, обработки запросов сервером. В куче хранятся будущие события, отсортированные по времени. Достаём ближайшее событие, обрабатываем, при необходимости планируем новые события — и снова в кучу.