Куча

Куча (англ. heap) — структура данных, которая позволяет быстро получать элемент с наивысшим приоритетом.

В этой заметке для определенности мы будем рассматривать мин-кучу: в ней в корне лежит минимальный элемент. Максимальная куча устроена полностью аналогично, нужно лишь развернуть все сравнения.

Куча поддерживает три основные операции:

  1. найти минимум;
  2. удалить минимум;
  3. добавить новый элемент.

Поэтому другое распространенное название этой структуры — очередь с приоритетами (англ. priority queue).

Кучи используются во многих алгоритмах. Например, они встречаются в алгоритмах поиска кратчайших путей, в алгоритме Прима и в сортировке кучей.

Устройство двоичной кучи

Самая популярная реализация очереди с приоритетами — двоичная куча (binary heap).

Ее удобно представлять как корневое дерево, для которого выполнены три свойства:

  1. значение в каждой вершине не больше значений в её детях;
  2. у каждой вершины не более двух детей;
  3. дерево заполнено по слоям сверху вниз и слева направо, без «дырок».

Третье свойство обычно называют полным двоичным деревом.

Важно понимать, что куча задается не единственным образом. Например, двух детей одной вершины часто можно менять местами, и свойство кучи не нарушится. Куча фиксирует не полный порядок элементов, а только локальное условие: родитель не больше детей.

Если в куче \(n\) элементов, то её высота равна \(\Theta(\log n)\): каждый следующий слой содержит примерно вдвое больше вершин, чем предыдущий.

Из-за этого основные операции имеют такие сложности:

  • найти минимум: \(O(1)\);
  • удалить минимум: \(O(\log n)\);
  • добавить элемент: \(O(\log n)\).

Помимо них часто рассматривают и другие операции, например изменение ключа, но пока нам достаточно этих трёх.

Хранение в массиве

У двоичной кучи есть очень удобное свойство: её можно хранить не указателями, а просто в массиве.

Будем использовать массив t с индексацией с единицы:

  • t[1] — корень;
  • у вершины с индексом k левый сын имеет индекс 2k;
  • правый сын имеет индекс 2k + 1;
  • родитель имеет индекс k / 2.

Нулевая ячейка массива в таком представлении не используется.

Восстановление свойства кучи

После изменения одного элемента куча может «сломаться» только на пути от этой вершины к корню или вниз к листьям. Поэтому достаточно уметь делать две вспомогательные операции.

Просеивание вверх

Если значение элемента уменьшилось, то, возможно, его нужно поднять выше. Для этого будем менять его местами с родителем, пока свойство кучи не восстановится.

void sift_up(int v) {
    while (v > 1 && t[v] < t[v / 2]) {
        swap(t[v], t[v / 2]);
        v /= 2;
    }
}

На каждом шаге вершина поднимается на один уровень вверх, поэтому время работы равно \(O(\log n)\).

Просеивание вниз

Если значение элемента увеличилось, то, наоборот, его нужно опустить вниз. Для этого будем менять его местами с меньшим из детей.

void sift_down(int v) {
    while (2 * v <= n) { // пока у вершины есть хотя бы левый сын
        int l = 2 * v;
        int r = 2 * v + 1;
        int u = l;

        if (r <= n && t[r] < t[l]) {
            u = r;
        }
        if (t[v] <= t[u]) {
            break;
        }

        swap(t[v], t[u]);
        v = u;
    }
}

Здесь мы тоже на каждом шаге спускаемся на один уровень ниже, поэтому асимптотика снова равна \(O(\log n)\).

Для интуиции полезно посмотреть визуализацию.

Основные операции

Теперь легко описать нужные нам операции над кучей:

  1. Найти минимум. Достаточно вернуть t[1], то есть значение в корне.
  2. Удалить минимум. Перенесем последний элемент массива в корень, уменьшим размер кучи и запустим sift_down(1).
  3. Добавить элемент. Положим новый элемент в конец массива и вызовем sift_up от его позиции.

Во всех случаях, кроме чтения минимума, нужно восстановить свойство кучи. Именно это и делают sift_up и sift_down.

Замечание. Можно рассматривать не только двоичные кучи, но и \(d\)-кучи, в которых у каждой вершины до \(d\) детей. Для любого фиксированного \(d\) высота всё равно остается логарифмической.

Построение кучи за линейное время

Построить кучу из \(n\) элементов можно двумя способами:

  • добавлять элементы по одному, тогда получится \(O(n \log n)\);
  • взять готовый массив и переупорядочить его в кучу за \(O(n)\).

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

void build_heap() {
    for (int i = n / 2; i >= 1; --i) {
        sift_down(i);
    }
}

Почему это корректно? Когда мы вызываем sift_down(i), оба поддерева вершины i уже являются кучами, потому что мы раньше обработали все вершины ниже. Значит, после sift_down(i) кучей становится и всё поддерево с корнем в i.

Почему это работает за \(O(n)\), а не за \(O(n \log n)\)? Потому что почти все вершины находятся низко:

  • листьев очень много, и они вообще не двигаются;
  • вершин на предпоследнем слое тоже много, но каждая может опуститься максимум на один уровень;
  • высоких вершин мало.

Почему это работает за \(O(n)\)? Давайте честно оценим сверху суммарное количество просеиваний вниз. У нас для каждой высоты \(i\) будет не больше \(2^{h - i}\) вершин на ней, а значит

\[ \sum_{i = 1}^h 2^{h - i} \cdot i = 2^{h + 1} - h - 2 \le 2 n - h - 2 \le 2 n = O(n) \]

Первое равенство несложно доказывается индукцией по \(h\).

Именно поэтому build_heap работает за линейное время.

Куча в стандартной библиотеке

В STL есть два популярных способа работать с кучами.

Алгоритмы над массивом

Функции make_heap, push_heap, pop_heap и sort_heap работают поверх массива или vector.

Важно: по умолчанию STL строит максимальную кучу, а не минимальную.

int ints[] = {10, 20, 30, 5, 15};
std::vector<int> v(ints, ints + 5);

std::make_heap(v.begin(), v.end());
v.front(); // максимальный элемент, то есть 30

std::pop_heap(v.begin(), v.end()); // максимум переместится в конец
v.pop_back();                      // теперь он действительно удален

v.push_back(99);
std::push_heap(v.begin(), v.end()); // восстановит свойство кучи

std::sort_heap(v.begin(), v.end()); // сортировка кучей

Контейнер priority_queue

Обычно напрямую с make_heap работают редко. Чаще используют контейнер priority_queue, который уже скрывает детали реализации.

std::priority_queue<int> q;

for (int x : {1, 5, 3, 4, 2, 0})
    q.push(x);

q.top(); // максимальный элемент, то есть 5
q.pop(); // удалить максимальный элемент

По умолчанию std::priority_queue<int> — это тоже максимальная куча.

Если нужна минимальная куча, можно написать так:

std::priority_queue<int, std::vector<int>, std::greater<int>> q;

У priority_queue операция чтения верхнего элемента работает за \(O(1)\), а добавление и удаление — за \(O(\log n)\). Кроме того, у него есть стандартные методы .size() и .empty().

Иногда вместо кучи используют структуры вроде std::set, особенно если нужно не только брать минимум, но и удалять произвольные элементы или аккуратно обновлять значения.