Биномиальная куча: операции и слияние за O(log n)

Биномиальная куча - структура данных типа «приоритетная очередь», которая поддерживает все стандартные операции кучи (insert, find-min, extract-min, decrease-key, delete) за $O(\log n)$ и при этом умеет дополнительно объединять две кучи (merge) за то же время. Бинарная куча на массиве этого не умеет: её слияние требует $O(n)$. Биномиальная куча относится к семейству mergeable heap и служит мостом между обычной бинарной кучей и более продвинутой Фибоначчиевой.

Биномиальное дерево $B_k$

Биномиальное дерево определяется рекурсивно:

• $B_0$ - одиночный узел.
• $B_k$ при $k \ge 1$ получается из двух копий $B_{k-1}$: одна копия становится самым левым ребёнком корня другой.

Иначе говоря, чтобы построить $B_3$, берут два $B_2$ и подвешивают второй к корню первого. Корень растущего дерева получает ещё одного сына, его степень увеличивается на единицу.

Из определения сразу следуют ключевые числовые свойства:

• В $B_k$ ровно $2^k$ узлов.
• Высота $B_k$ равна $k$.
• На глубине $i$ (от $0$ до $k$) находится $\binom{k}{i}$ узлов - отсюда и имя «биномиальное».
• Степень корня $B_k$ равна $k$, и его дети - корни деревьев $B_{k-1}, B_{k-2}, \dots, B_0$ в порядке убывания ранга.

Эти свойства легко доказываются индукцией: при склейке двух $B_{k-1}$ удваивается число узлов ($2 \cdot 2^{k-1} = 2^k$), а число элементов на уровне $i$ нового дерева складывается из элементов уровня $i$ старого дерева и уровня $i-1$ второго - это тождество Паскаля $\binom{k}{i} = \binom{k-1}{i} + \binom{k-1}{i-1}$.

Биномиальная куча как лес

Биномиальная куча размера $n$ - это лес биномиальных деревьев, удовлетворяющий двум условиям:

1. Heap-order property. В каждом дереве ключ родителя не больше ключа любого ребёнка (для min-кучи). Минимум всей кучи лежит в корне одного из деревьев.
2. Уникальность рангов. В лесу не может быть двух деревьев с одинаковым $k$. Если $n = (b_t b_{t-1} \dots b_1 b_0)_2$ в двоичной записи, то $B_k$ присутствует в куче тогда и только тогда, когда $b_k = 1$.

Это даёт прямое соответствие «куча размера $n$» $\leftrightarrow$ «двоичная запись $n$». Число деревьев в лесу не превосходит $\lfloor \log_2 n \rfloor + 1$ - именно поэтому все операции укладываются в логарифм.

Корни деревьев соединяют в односвязный список, упорядоченный по возрастанию ранга. У каждого узла хранят ключ, степень, указатель на родителя, на самого левого ребёнка и на правого «брата» (sibling).

Объединение двух куч как сложение двоичных чисел

Операция merge - сердце биномиальной кучи. Пусть есть две кучи $H_1$ размера $n_1$ и $H_2$ размера $n_2$. Их корневые списки уже отсортированы по рангу - сначала их сливают в один список (как в merge-sort, за $O(\log n)$).

Затем по списку идут слева направо и применяют правило: если встречаются два соседних дерева одинакового ранга $k$, их сливают в одно дерево $B_{k+1}$ - корень с большим ключом становится ребёнком корня с меньшим. Это даёт «перенос» в следующий разряд - ровно как при сложении $n_1 + n_2$ в двоичной системе.

Аккуратность нужна, когда подряд идут три дерева ранга $k$: тогда первое оставляют как есть, а второе и третье склеивают (это соответствует случаю $1+1+1=11_2$ при сложении в столбик с уже имеющимся переносом). В итоге результирующий лес снова состоит из деревьев с уникальными рангами, а суммарное время - $O(\log(n_1 + n_2))$.

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

Через merge выражаются почти все остальные операции.

• find-min - пройти по корневому списку, выбрать минимум среди $\le \log n + 1$ корней. Время: $O(\log n)$. Если хранить указатель на минимальный корень и обновлять его при каждой модификации, получается $O(1)$ amortized.
• insert(x) - создать однонодовую кучу-сингл $B_0$ и слить её с основной. Амортизированно $O(1)$, в худшем случае $O(\log n)$.
• extract-min - найти корень с минимальным ключом, удалить его из корневого списка, перевернуть список его детей (они идут $B_{k-1}, B_{k-2}, \dots, B_0$, а для merge нужен возрастающий порядок) и слить полученный лес с оставшейся частью. Время: $O(\log n)$.
• decrease-key(v, k') - заменить ключ узла $v$ на меньший $k'$ и «всплыть» вверх, обменивая местами с родителем, пока heap-order не восстановится. Высота не превышает $\log n$, отсюда $O(\log n)$. Реальные данные при swap переносить накладно - обычно меняют только значения ключей и сателлитные данные.
• delete(v) - выполняется как decrease-key(v, -\infty) с последующим extract-min. Тоже $O(\log n)$.
• build из массива - последовательные insert дают $O(n)$ амортизированно (геометрическая сумма переносов аналогична построению бинарной кучи).

Сводная таблица сложностей:

$$\begin{aligned} \text{insert} &: O(1)\ \text{amort.},\ O(\log n)\ \text{worst} \\ \text{find-min} &: O(\log n)\ (\text{или}\ O(1)\ \text{с указателем}) \\ \text{extract-min} &: O(\log n) \\ \text{merge} &: O(\log n) \\ \text{decrease-key} &: O(\log n) \\ \text{delete} &: O(\log n) \end{aligned}$$

Ленивая версия и Фибоначчиева куча

Если откладывать «приведение в порядок» (объединение деревьев одинаковых рангов) до момента extract-min, получится ленивая биномиальная куча: insert и merge становятся $O(1)$ в худшем случае, а вся работа концентрируется в extract-min, который теперь amortized $O(\log n)$. На этой идее построена Фибоначчиева куча (Fredman, Tarjan, 1984): она добавляет каскадные срезы при decrease-key и достигает амортизированного $O(1)$ для всех операций, кроме extract-min и delete ($O(\log n)$ amortized).

Фибоначчиева куча асимптотически лучше биномиальной для алгоритма Дейкстры на плотных графах, но имеет большие константы и сложнее в реализации - поэтому в учебных и инженерных задачах биномиальная куча остаётся компромиссом «простота против гибкости».

Где применяется

• Алгоритмы кратчайших путей и MST. Дейкстра и Прим на разреженных графах - там, где decrease-key вызывается часто. Биномиальная куча даёт $O((|V| + |E|) \log |V|)$.
• Mergeable priority queue. Когда задачи разбиваются по подсистемам и затем нужно объединить их очереди - например, в распределённых системах или при слиянии планировщиков двух процессов.
• Дискретно-событийное моделирование. Когда несколько генераторов событий ведут отдельные очереди, которые объединяются в общую таймлайн.
• Branch-and-bound / A* с подзадачами. Подзадачи каждого поддерева можно держать в собственной куче и сливать при обходе.

Сравнение: бинарная, биномиальная, Фибоначчиева

Бинарная куча выигрывает по константам и локальности памяти, но проигрывает там, где нужны частые слияния. Биномиальная - сбалансированный «mergeable» вариант. Фибоначчиева оптимальна асимптотически, но дорога в реализации и константах.

Частые ошибки

• Путают $B_k$ с полным бинарным деревом высоты $k$. В $B_k$ ровно $2^k$ узлов, а в полном бинарном дереве высоты $k$ их $2^{k+1}-1$. Структуры разные: у $B_k$ корень имеет степень $k$.
• Считают, что в куче может быть несколько деревьев одного ранга. Нет - это нарушает инвариант, ровно как «две единицы в одном разряде» нарушают двоичную запись. Любая операция, нарушившая правило, обязана выполнить серию сливаний.
• Забывают развернуть список детей при extract-min. Дети корня хранятся в порядке убывания ранга, а корневой список - в порядке возрастания. Без разворота merge даст неверный лес.
• Пытаются делать decrease-key через указатель в массив. В биномиальной куче нет фиксированного массива: чтобы быстро найти узел по «дескриптору», операция insert должна возвращать handle на конкретный узел, а пользователь обязан хранить его.
• Меряют производительность только по асимптотике. На малых $n$ и без merge бинарная куча почти всегда быстрее: меньше указателей, лучше кэш.

FAQ

Чем биномиальная куча отличается от бинарной? Бинарная - это массив с heap-order, она проста и кэш-дружелюбна, но merge требует $O(n)$. Биномиальная - лес деревьев, merge за $O(\log n)$ ценой указательной структуры и больших констант.

Почему именно «биномиальная»? Потому что на глубине $i$ дерева $B_k$ ровно $\binom{k}{i}$ узлов - биномиальный коэффициент. Это прямо следует из рекурсивного определения и тождества Паскаля.

Когда выбирать биномиальную, а когда Фибоначчиеву? Если в алгоритме доминирует decrease-key (плотные графы в Дейкстре, специальные алгоритмы MST) - Фибоначчиева теоретически быстрее. Если важна простота, отладка и предсказуемость - биномиальная или даже бинарная.

Коротко

Биномиальная куча - лес биномиальных деревьев $B_k$ с уникальными рангами и heap-order; число и форма деревьев определяются двоичной записью $n$. Все базовые операции работают за $O(\log n)$, а ключевая merge сводится к сложению двоичных чисел с переносами. Это удобная mergeable-структура, более гибкая, чем бинарная куча, и более простая в реализации, чем Фибоначчиева.