Двоичная куча - Алгоритмика

Куча (англ. heap) — абстрактная структура данных, поддерживающая следующие операции:

Нахождение минимума.
Удаление минимума.
Добавление нового элемента в кучу.

Другое название, лучше отражающее функциональность — очередь с приоритетами (англ. priority queue).

Кучи используются во многих алгоритмах. Например, кучи используются в алгоритмах поиска кратчайшего пути, а также с помощью кучи можно проводить сортировку (путём превращения массива в кучу, а кучу в отсортированный массив).

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

Двоичная куча (пирамида, сортирующее дерево, англ. binary heap) — реализация очереди с приоритетами, использующая корневое дерево, для которого выполнены три условия:

Значение в любой вершине не больше, чем значения её потомков.
У любой вершины не более двух сыновей.
Слои заполняются последовательно сверху вниз и слева направо, без «дырок».

Заметим, что двоичная куча строится неоднозначно: например, значения сыновей, которые являются листами, всегда можно менять местами. Фиксирована только сама структура и предикат «родитель не больше детей».

Обозначим высоту дерева как $h$. Так как куча всегда состоит из нескольких слоев заполненных полностью и одного заполненного частично, и каждый следующий слой содержит в два раза больше вершин, чем предыдущий, то высота дерева будет $\Theta(\log n)$.

Как и любая очередь с приоритетами, двоичная куча должна уметь выполнять операции:

Нахождение минимума за $O(1)$.
Удаление минимума за $O(h)$.
Добавление нового элемента в кучу за $O(h)$.

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

#Реализация

Хранить кучу будем в виде массива $t$, где у корня индекс равен $1$, а у вершины $k$ индексы ее детей равны $2k$ и $(2k + 1)$. Нулевая ячейка массива при этом остается пустой.

Дальше определим две вспомогательные функции, которые восстанавливают инварианты кучи при изменении значения одного элемента.

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

void sift_up(int v) {
    // если элемент больше своего отца, то всё корректно и больше ничего делать не нужно
    while (v > 1 && t[v] < t[v / 2]) {
        // иначе меняем его с отцом и запускаемся от отца
        swap(t[v], t[v / 2]);
        v /= 2;
    }
}

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

void sift_down(int v) {
    // пока не пришли в лист
    while (2 * v <= n) { // n -- количество элементов в куче
        int l = 2 * v; // левый сын
        int r = 2 * v + 1; // правый сын
        // если правый сын существует и меньше, выбираем его
        int u = (r <= n && t[r] < t[l] ? r : l);
        if (t[v] <= t[u])
            break; // инвариант и так выполняется, завершаемся
        swap(t[v], t[u]);
        v = u;
   }
}

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

Вернемся теперь к «полезным» операциям:

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

Примечание. Если рассматривать не двоичную кучу, а так называемую $d$-кучу, в которой у каждой вершины может быть не более $d$ сыновей, то время работы останется таким же для любой константы $d$.

#Построение за линейное время

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

Мы на самом деле хотим просто переупорядочить элементы некоторого массива $t$ так, чтобы для любого индекса $1 \le i \le n$ выполнялись неравенства $t_i \le t_{2 i}$ и $t_i \le t_{2 i + 1}$ (если, конечно, соответствующие элементы существуют).

Давайте тогда это свойство кучи восстанавливать с конца: будем постепенно увеличивать суффикс, на котором выполняется свойство, с помощью просеивания вниз (sift_down). Получаем следующий алгоритм:

void build_heap() {
    for (int i = n; i > 0; --i) {
        // для суффикса t[i + 1 .. n] свойство кучи выполняется
        sift_down(i);
        // теперь выполняется для суффикса t[i .. 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$.

#В стандартной библиотеке

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

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

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

pop_heap(v.begin(), v.end()); // удалить максимум из кучи
v.pop_back(); // уменьшить размер массива на единицу

v.push_back(99); // добавить элемент в конец массива
push_heap(v.begin(), v.end()); // вызовет sift_up от последнего элемента

sort_heap(v.begin(), v.end()); // сортировка кучей: в v будет записан отсортированный массив

Однако напрямую они используются довольно редко. Чаще используется интерфейс поверх вектора и этих операций, доступный как priority_queue:

priority_queue<int> q;

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

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

В priority_queue нахождение максимального (по умолчанию) элемента работает за $O(1)$, а добавление и удаление за $O(\log n)$. Помимо этого у него есть методы .size(), .empty() и все остальные, ожидаемые от контейнеров STL.

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