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

TL;DR

Биномиальная куча (binomial heap; синоним — «биномиальная пирамида») — очередь с приоритетом из леса биномиальных деревьев [math]\displaystyle{ B_0, B_1, \dots }[/math], где дерево [math]\displaystyle{ B_k }[/math] содержит ровно [math]\displaystyle{ 2^k }[/math] узлов. Кучей из [math]\displaystyle{ n }[/math] элементов управляет та же двоичная логика, что и счётчиком: набор деревьев в точности соответствует единичным битам числа [math]\displaystyle{ n }[/math]. Главное преимущество перед двоичной кучей — быстрое слияние двух куч за [math]\displaystyle{ O(\log n) }[/math] (вместо [math]\displaystyle{ \Theta(n) }[/math]) и амортизированная вставка за [math]\displaystyle{ O(1) }[/math]. Извлечение минимума и уменьшение ключа стоят [math]\displaystyle{ O(\log n) }[/math]; уменьшение ключа не доводится до [math]\displaystyle{ O(1) }[/math] (это уже свойство фибоначчиевой кучи). Биномиальная куча — классический мостик между двоичной и фибоначчиевой кучами и удобная структура там, где очереди с приоритетом приходится объединять.

Свойство	Значение
Класс	Лес биномиальных деревьев, связанных в список корней; реализация очереди с приоритетом
Изобретение	Ж. Вюйемен, 1978 [2]; реализация и анализ — М. Браун, 1978 [3]
Insert	[math]\displaystyle{ O(\log n) }[/math] худший, амортизированно [math]\displaystyle{ O(1) }[/math]
Find-Min	[math]\displaystyle{ O(\log n) }[/math]; [math]\displaystyle{ O(1) }[/math] при хранении указателя
Extract-Min	[math]\displaystyle{ O(\log n) }[/math]
Decrease-Key	[math]\displaystyle{ O(\log n) }[/math]
Union / Merge	[math]\displaystyle{ O(\log n) }[/math]
Delete	[math]\displaystyle{ O(\log n) }[/math] (decrease-key + extract-min)
Память	[math]\displaystyle{ O(n) }[/math]; на узел — degree, parent, child, sibling
Упорядоченность	Частичная: в каждом дереве — min-куча; минимум среди корней
Стабильность	Неприменима
Альтернативы	Двоичная куча (быстрее на практике), фибоначчиева и pairing-кучи (быстрее `decrease-key`), левосторонняя и скошенная кучи
Где встречается	Dijkstra и Prim на разреженных графах, слияние очередей событий, Boost.Heap (`binomial_heap`), учебная база для фибоначчиевых куч

Определения

Биномиальное дерево (binomial tree) [math]\displaystyle{ B_0, B_1, B_2, \dots }[/math] определяется рекурсивно:

[math]\displaystyle{ B_0 }[/math] — одно дерево из одного узла;
[math]\displaystyle{ B_k }[/math] получается слиянием двух [math]\displaystyle{ B_{k-1} }[/math]: корень одного становится крайним левым ребёнком корня другого. Эквивалентно: [math]\displaystyle{ B_k }[/math] — корень, дети которого (слева направо) есть [math]\displaystyle{ B_{k-1}, B_{k-2}, \dots, B_0 }[/math].

Свойства [math]\displaystyle{ B_k }[/math] (доказываются индукцией, см. раздел «Корректность и оценка сложности»):

Параметр	Значение
Число узлов	[math]\displaystyle{ 2^k }[/math]
Высота	[math]\displaystyle{ k }[/math]
Степень корня	[math]\displaystyle{ k }[/math]
Число узлов на глубине [math]\displaystyle{ i }[/math]	[math]\displaystyle{ \binom{k}{i} }[/math] (биномиальный коэффициент — отсюда название)

Биномиальная куча (binomial heap) — набор (лес) биномиальных деревьев, для которого выполнено:

Каждое дерево — min-куча: ключ родителя не больше ключей детей.
Не более одного дерева каждой степени: среди корней нет двух деревьев с одинаковым degree. Степени корней в списке строго возрастают.

Из второго условия и равенства «[math]\displaystyle{ B_k }[/math] содержит [math]\displaystyle{ 2^k }[/math] узлов» следует, что набор степеней в куче из [math]\displaystyle{ n }[/math] элементов — это в точности множество единичных битов числа [math]\displaystyle{ n }[/math]. Поэтому деревьев не больше [math]\displaystyle{ \lfloor \log_2 n \rfloor + 1 }[/math].

Узел хранит поля: key, degree (число детей), parent, child (первый ребёнок), sibling (следующий узел в списке детей либо в списке корней). Список корней — связный через sibling список, упорядоченный по возрастанию degree; его голова — точка входа в кучу.

Обозначения. [math]\displaystyle{ n }[/math] — число элементов; [math]\displaystyle{ \log }[/math] — по основанию 2. Узлы-корни перечисляются в порядке возрастания степени. NIL — пустая ссылка.

Рис. 1. Биномиальные деревья [math]\displaystyle{ B_0 }[/math]–[math]\displaystyle{ B_3 }[/math]. Дерево [math]\displaystyle{ B_k }[/math] — корень, чьи дети суть деревья [math]\displaystyle{ B_{k-1},\dots,B_0 }[/math]; число узлов равно [math]\displaystyle{ 2^k }[/math], степень корня равна [math]\displaystyle{ k }[/math].

Мотивация и интуиция

Двоичная куча идеальна как одиночная очередь с приоритетом, но сливать две кучи она не умеет: чтобы объединить две двоичные кучи, приходится перестраивать массив за [math]\displaystyle{ \Theta(n) }[/math]. Между тем слияние нужно часто: параллельные потоки объединяют локальные очереди, потоковая обработка подключает новые источники, графовые алгоритмы работают с несколькими компонентами.

Биномиальная куча решает именно эту задачу. Идея в том, чтобы держать не одно почти полное дерево, а коллекцию деревьев удваивающегося размера, как разряды двоичного числа. Вставка небольшого элемента почти всегда создаёт новое дерево [math]\displaystyle{ B_0 }[/math]; лишь изредка «перенос» пробегает несколько разрядов, сливая деревья равной степени. Это в точности сложение единицы с двоичным счётчиком: отдельный перенос может стоить [math]\displaystyle{ O(\log n) }[/math], но амортизированно вставка стоит [math]\displaystyle{ O(1) }[/math]. Слияние двух куч — это сложение двух счётчиков, то есть [math]\displaystyle{ O(\log n) }[/math].

Ключевая мысль: вместо того чтобы после каждой операции восстанавливать форму одного дерева, куча хранит множество деревьев разных степеней и объединяет равные по ходу дела. Степень корня (размер дерева) играет роль разряда.

Устройство

Биномиальная куча — это лес, а не одно дерево (см. рис. 1). Компоненты:

Биномиальные деревья [math]\displaystyle{ B_k }[/math], по одному на каждый единичный бит числа элементов.
Список корней, связанный через sibling и упорядоченный по возрастанию degree.
Поля узла: degree, parent, child, sibling — благодаря им соседние деревья равной степени легко находятся и сливаются за [math]\displaystyle{ O(1) }[/math].

Минимум кучи лежит в одном из корней (каждый корень — минимум своего дерева). Значит, Find-Min просматривает список корней за [math]\displaystyle{ O(\log n) }[/math] (или [math]\displaystyle{ O(1) }[/math], если хранить отдельный указатель на минимум). У всех узлов одного дерева степень согласована: degree узла равен числу его детей, а само дерево с корнем степени [math]\displaystyle{ k }[/math] — это ровно [math]\displaystyle{ B_k }[/math].

Соответствие с двоичным счётчиком — центральное: [math]\displaystyle{ n = 13 = 1101_2 = 8 + 4 + 1 }[/math] — единичные биты стоят в разрядах 3, 2 и 0, поэтому в куче есть деревья [math]\displaystyle{ B_3 }[/math], [math]\displaystyle{ B_2 }[/math] и [math]\displaystyle{ B_0 }[/math], а в списке корней они идут по возрастанию степени — [math]\displaystyle{ B_0, B_2, B_3 }[/math] (рис. 2). Число деревьев равно числу единичных битов, то есть не превосходит [math]\displaystyle{ \lfloor \log_2 n \rfloor + 1 }[/math].

Рис. 2. Куча из 13 элементов — это деревья [math]\displaystyle{ B_0 }[/math], [math]\displaystyle{ B_2 }[/math], [math]\displaystyle{ B_3 }[/math] (степени 0, 2, 3), как разряды числа [math]\displaystyle{ 13 = 2^3 + 2^2 + 2^0 }[/math]. Корни связаны в список по возрастанию степени.

Операции и алгоритмы

Операция: слияние двух деревьев (Link)

Идея. Если два корня имеют одинаковую степень [math]\displaystyle{ k-1 }[/math], их деревья — это два [math]\displaystyle{ B_{k-1} }[/math]. Делаем корень с меньшим ключом родителем другого: получается [math]\displaystyle{ B_k }[/math] (см. рис. 3). Свойство кучи при этом сохраняется.

Пошаговое описание.

Требуется degree[y] = degree[z] = k-1 и key[z] ≤ key[y].
Присоединить [math]\displaystyle{ y }[/math] первым ребёнком к [math]\displaystyle{ z }[/math].
Увеличить degree[z] на 1.

Инвариант. После операции дерево с корнем [math]\displaystyle{ z }[/math] — корректное [math]\displaystyle{ B_k }[/math], а свойство min-кучи выполнено (ключ [math]\displaystyle{ z }[/math] не больше ключа [math]\displaystyle{ y }[/math], а поддеревья — уже кучи).

Псевдокод.

Алгоритм Binomial-Link(y, z)
Вход:  корни y, z деревьев B_{k−1}; degree[y] = degree[z] = k−1; key[z] ≤ key[y]
Выход: дерево B_k с корнем z
1  parent[y] ← z
2  sibling[y] ← child[z]
3  child[z] ← y
4  degree[z] ← degree[z] + 1

Сложность: O(1) времени и памяти.
Корректность: y становится (крайним левым) ребёнком z; форма B_k соблюдена,
свойство min-кучи сохранено, так как key[z] ≤ key[y].

Крайний случай. Связывать можно только деревья равной степени — иначе форма [math]\displaystyle{ B_k }[/math] не получится. Равные ключи допустимы (сравнение нестрогое).

Рис. 3. Binomial-Link: из двух [math]\displaystyle{ B_1 }[/math] получается [math]\displaystyle{ B_2 }[/math]. Меньший корень 3 становится родителем 5; degree(3) увеличивается с 1 до 2.

Операция: объединение куч (Union)

Идея. Слить два списка корней в один (по возрастанию степени), затем одним проходом «консолидировать»: если рядом оказались два дерева одинаковой степени, слить их через Link. Это вычитание повторяющихся разрядов — как сложение двух чисел по разрядам.

Пошаговое описание.

Merge-Root-Lists — слить два отсортированных по degree списка (как в merge sort).
Пройти консолидацию слева направо; для текущей пары x, next:
- если degree[x] ≠ degree[next] либо следующий за next тоже имеет степень degree[x] — просто сдвинуться;
- иначе связать x и next через Link (родителем становится меньший ключ), учитывая три дерева одного размера подряд.
После прохода степени корней попарно различны.

Инвариант. На каждом шаге консолидации все деревья левее текущей позиции имеют попарно различные степени, а слияние равных степеней не нарушает свойство min-кучи.

Псевдокод.

Алгоритм Binomial-Heap-Union(H1, H2)
Вход:  H1, H2 — биномиальные кучи
Выход: куча со всеми элементами H1 и H2; степени корней различны
Инвариант: список корней упорядочен по degree; левее x степени различны

1  H ← Make-Binomial-Heap()
2  head[H] ← Merge-Root-Lists(H1, H2)         # слияние по возрастанию degree
3  if head[H] = NIL
4      return H
5  prev ← NIL
6  x ← head[H]
7  next ← sibling[x]
8  while next ≠ NIL
9      if degree[x] ≠ degree[next] or
           (sibling[next] ≠ NIL and degree[sibling[next]] = degree[x])
10         prev ← x
11         x ← next
12     else if key[x] ≤ key[next]
13         sibling[x] ← sibling[next]
14         Binomial-Link(next, x)             # x — родитель next
15     else
16         if prev = NIL
17             head[H] ← next
18         else
19             sibling[prev] ← next
20         Binomial-Link(x, next)             # next — родитель x
21         x ← next
22     next ← sibling[x]
23 return H

Сложность: O(log n) времени (слияние двух списков длины O(log n) и один проход).
Корректность: после прохода рядом не остаётся деревьев равной степени, поэтому
куча удовлетворяет обоим условиям определения; элементы сохраняются (Link не теряет узлов).

Разбор на примере. Пусть [math]\displaystyle{ H_1 }[/math] даёт деревья степеней [math]\displaystyle{ \{0, 1\} }[/math], а [math]\displaystyle{ H_2 }[/math] — [math]\displaystyle{ \{0, 1\} }[/math]. После слияния списков: [math]\displaystyle{ B_0, B_0, B_1, B_1 }[/math]. Консолидация: две [math]\displaystyle{ B_0 }[/math] сливаются в [math]\displaystyle{ B_1 }[/math]; теперь три [math]\displaystyle{ B_1 }[/math] подряд, и две из них сливаются в [math]\displaystyle{ B_2 }[/math] — остаётся по одному дереву каждой степени. На рис. 4 показан другой случай: в слитом списке корней стоят [math]\displaystyle{ B_0 }[/math] с ключом 4, [math]\displaystyle{ B_0 }[/math] с ключом 7, [math]\displaystyle{ B_1 }[/math] с ключом 2 и [math]\displaystyle{ B_2 }[/math] с ключом 9 (всего 8 элементов), и в итоге получается одно дерево [math]\displaystyle{ B_3 }[/math]. Случай трёх деревьев равной степени, из-за которого в строке 9 стоит проверка sibling[next], — рис. 5.

Крайние случаи. Объединение с пустой кучей возвращает вторую без изменений. Три дерева равной степени подряд обрабатываются с учётом sibling[next] (строка 9), чтобы не слить не те деревья.

Рис. 4. Binomial-Heap-Union: списки корней сливаются по степени, затем равные степени снова и снова связываются через Link, пока не останется по одному дереву на степень.

Рис. 5. Три дерева [math]\displaystyle{ B_1 }[/math] подряд: проверка sibling[next] пропускает первую пару, поэтому связываются две последние. Иначе в списке оказалось бы [math]\displaystyle{ B_2 }[/math] перед [math]\displaystyle{ B_1 }[/math], и степени перестали бы возрастать.

Операция: вставка (Insert)

Идея. Создать новое дерево [math]\displaystyle{ B_0 }[/math] из одного узла и объединить его с кучей. Это в точности прибавление единицы к двоичному счётчику: обычно добавление ограничивается новым [math]\displaystyle{ B_0 }[/math], изредка «перенос» сливает несколько деревьев.

Пошаговое описание.

Создать узел [math]\displaystyle{ x }[/math] с ключом [math]\displaystyle{ k }[/math] (degree = 0).
Выполнить Union(H, {x}).

Инвариант. То же, что у Union.

Псевдокод.

Алгоритм Binomial-Heap-Insert(H, k)
Вход:  H — биномиальная куча; k — вставляемый ключ
Выход: куча с добавленным k
1  H' ← Make-Binomial-Heap()
2  head[H'] ← новый узел с ключом k и degree = 0
3  H ← Binomial-Heap-Union(H, H')

Сложность: O(log n) в худшем случае (перенос через все разряды),
амортизированно O(1).  Память O(1).
Корректность: следует из корректности Union.

Разбор на примере. При вставке восьмого элемента в кучу из семи ([math]\displaystyle{ 111_2 }[/math]) все три дерева [math]\displaystyle{ B_0, B_1, B_2 }[/math] последовательно сливаются, и получается одно [math]\displaystyle{ B_3 }[/math] ([math]\displaystyle{ 1000_2 }[/math]), рис. 6.

Крайние случаи. В пустую кучу вставка создаёт единственное [math]\displaystyle{ B_0 }[/math]. Если младший разряд нулевой (чётное [math]\displaystyle{ n }[/math]), переноса нет и вставка фактически [math]\displaystyle{ O(1) }[/math].

Рис. 6. Вставка — это «[math]\displaystyle{ 111_2 + 1 = 1000_2 }[/math]»: три дерева сливаются в одно [math]\displaystyle{ B_3 }[/math]. Худший случай [math]\displaystyle{ O(\log n) }[/math], но амортизированно [math]\displaystyle{ O(1) }[/math].

Операция: поиск минимума (Find-Min)

Идея. Минимум кучи — минимум ключей корней деревьев. Достаточно просмотреть список корней.

Алгоритм Binomial-Heap-Minimum(H)
Вход:  H — биномиальная куча
Выход: узел с минимальным ключом либо NIL, если куча пуста
Инвариант: y — корень с минимальным ключом среди уже просмотренных корней
1  y ← NIL
2  x ← head[H]
3  while x ≠ NIL
4      if y = NIL or key[x] < key[y]
5          y ← x
6      x ← sibling[x]
7  return y

Сложность: O(log n) — не более ⌊log₂ n⌋ + 1 корней. O(1), если хранить указатель на минимум.

Операция: извлечение минимума (Extract-Min)

Идея. Найти корень с минимальным ключом, удалить его, а его детей — деревья [math]\displaystyle{ B_{k-1}, \dots, B_0 }[/math] — сделать новыми корнями и объединить с остальной кучей. Детей нужно перевернуть, чтобы список шёл по возрастанию степени.

Пошаговое описание.

Найти корень [math]\displaystyle{ x }[/math] с минимальным ключом в списке корней.
Удалить [math]\displaystyle{ x }[/math] из списка корней.
Список детей [math]\displaystyle{ x }[/math] (идёт как [math]\displaystyle{ B_{k-1}, \dots, B_0 }[/math]) развернуть в возрастающий порядок (см. рис. 7).
У каждого ребёнка обнулить parent.
Выполнить Union(H, H'), где [math]\displaystyle{ H' }[/math] — список детей.
Вернуть ключ [math]\displaystyle{ x }[/math].

Инвариант. Дети корня — корректные деревья-кучи; после разворота их степени возрастают, так что применим Union.

Псевдокод.

Алгоритм Binomial-Heap-Extract-Min(H)
Вход:  H — непустая биномиальная куча
Выход: минимальный ключ; куча без этого элемента
1  x ← корень с минимальным ключом
2  H' ← Make-Binomial-Heap()
3  head[H'] ← Reverse-Siblings(child[x])      # дети B_{k−1},…,B₀ → по возрастанию degree
4  для каждого ребёнка c в head[H']  parent[c] ← NIL
5  удалить x из списка корней H
6  H ← Binomial-Heap-Union(H, H')
7  return key[x]

Сложность: O(log n) времени (не более ⌊log₂ n⌋ детей и слияние за O(log n)).
Корректность: оставшиеся деревья — min-кучи, дети x — тоже; Union восстанавливает
условие единственности степени, ничего не теряя.

Крайние случаи. Единственный элемент — куча становится пустой. Если минимальный корень — это [math]\displaystyle{ B_0 }[/math] (без детей), Union просто удаляет его.

Рис. 7. Extract-Min: корень-минимум удаляется, его дети [math]\displaystyle{ B_{k-1},\dots,B_0 }[/math] становятся отдельными корнями (в порядке возрастания степени) и объединяются с остальной кучей.

Операция: уменьшение ключа (Decrease-Key)

Идея. Уменьшить ключ узла и «поднимать» его вверх, пока он меньше родителя, обмениваясь ключами. Путь вверх в дереве [math]\displaystyle{ B_k }[/math] не длиннее [math]\displaystyle{ k \le \log n }[/math].

Пошаговое описание.

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

Инвариант. После обмена ключами нарушение свойства кучи может остаться только на ребре между y и parent[y]; всё, что ниже, уже корректно.

Алгоритм Binomial-Heap-Decrease-Key(H, x, k)
Вход:  x — узел кучи H; k — новый ключ, k ≤ key[x]
Выход: ключ x уменьшен, свойства кучи восстановлены
1  if k > key[x]
2      error "новый ключ больше текущего"
3  key[x] ← k
4  y ← x
5  z ← parent[y]
6  while z ≠ NIL and key[y] < key[z]
7      swap(key[y], key[z])
8      y ← z
9      z ← parent[y]

Сложность: O(log n).   Память O(1).
Корректность: обмен с родителем восстанавливает свойство на текущем уровне,
нарушение может остаться только выше; цикл идёт до корня дерева.

Удаление произвольного узла сводится к уменьшению ключа до [math]\displaystyle{ -\infty }[/math] с последующим Extract-Min: Delete(H, x) = Extract-Min(H после Decrease-Key(x, −∞)), за [math]\displaystyle{ O(\log n) }[/math].

Операция: создание кучи (Make-Heap)

Пустая куча — это head[H] = NIL за [math]\displaystyle{ O(1) }[/math]. Заметим: в отличие от двоичной кучи, «построить кучу из [math]\displaystyle{ n }[/math] элементов» здесь — это [math]\displaystyle{ n }[/math] вставок, суммарно [math]\displaystyle{ O(n) }[/math] амортизированно (а не быстрее), поскольку каждая вставка амортизированно [math]\displaystyle{ O(1) }[/math].

Реализация структуры на C++

Класс min-кучи: узлы с полями degree, parent, child, sibling, список корней через sibling, операции push, pop, decreaseKey, merge, top, contains. Метод validate() проверяет оба условия определения (heap-свойство, размер дерева [math]\displaystyle{ 2^k }[/math], строгое возрастание степеней корней, корректность ссылок).

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <stdexcept>
#include <limits>

template <typename T>
class BinomialHeap {
public:
    struct Node {
        T key;
        int degree;
        Node* parent;
        Node* child;    // первый ребёнок
        Node* sibling;  // следующий сосед / следующий корень
        explicit Node(const T& k)
            : key(k), degree(0), parent(nullptr), child(nullptr), sibling(nullptr) {}
    };

private:
    Node* head_ = nullptr;   // корни; degree строго возрастает

    static Node* mergeLists(Node* a, Node* b) {
        Node* head = nullptr;
        Node** tail = &head;
        while (a && b) {
            Node*& pick = (a->degree <= b->degree) ? a : b;
            *tail = pick;
            pick = pick->sibling;
            tail = &((*tail)->sibling);
        }
        *tail = a ? a : b;
        return head;
    }

    // z становится родителем y; требуется degree[y] == degree[z] и key[z] <= key[y]
    static void link(Node* y, Node* z) {
        y->parent = z;
        y->sibling = z->child;
        z->child = y;
        z->degree += 1;
    }

    static Node* unionLists(Node* h1, Node* h2) {
        Node* head = mergeLists(h1, h2);
        if (!head) return nullptr;
        Node* prev = nullptr;
        Node* x = head;
        Node* next = x->sibling;
        while (next) {
            if (x->degree != next->degree ||
                (next->sibling && next->sibling->degree == x->degree)) {
                prev = x;
                x = next;
            } else if (x->key <= next->key) {
                x->sibling = next->sibling;
                link(next, x);
            } else {
                if (!prev) head = next;
                else prev->sibling = next;
                link(x, next);
                x = next;
            }
            next = x->sibling;
        }
        return head;
    }

    // отсоединить корень x (дети становятся корнями) и удалить узел
    void detachRoot(Node* x) {
        Node* prev = nullptr;
        Node* cur = head_;
        while (cur && cur != x) { prev = cur; cur = cur->sibling; }
        if (cur != x) return;
        if (prev) prev->sibling = x->sibling;
        else head_ = x->sibling;
        Node* childList = nullptr;
        for (Node* c = x->child; c; ) {          // разворот: возрастание degree
            Node* nxt = c->sibling;
            c->parent = nullptr;
            c->sibling = childList;
            childList = c;
            c = nxt;
        }
        head_ = unionLists(head_, childList);
        delete x;
    }

    static void destroyNodes(Node* n) {
        while (n) {
            Node* next = n->sibling;
            destroyNodes(n->child);
            delete n;
            n = next;
        }
    }

    bool checkNode(Node* n, long long& size) const {
        size = 1;
        int children = 0;
        for (Node* c = n->child; c; c = c->sibling) {
            if (c->parent != n) return false;
            if (c->key < n->key) return false;          // min-куча
            long long sub;
            if (!checkNode(c, sub)) return false;
            size += sub;
            ++children;
        }
        if (children != n->degree) return false;
        if (size != (1LL << n->degree)) return false;    // размер B_k = 2^k
        return true;
    }

    static Node* findNode(Node* n, const T& k) {
        if (!n) return nullptr;
        if (n->key == k) return n;
        if (Node* r = findNode(n->child, k)) return r;
        return findNode(n->sibling, k);
    }

public:
    BinomialHeap() = default;
    ~BinomialHeap() { destroyNodes(head_); }
    BinomialHeap(const BinomialHeap&) = delete;
    BinomialHeap& operator=(const BinomialHeap&) = delete;

    bool empty() const { return head_ == nullptr; }

    const T& top() const {
        if (!head_) throw std::out_of_range("пустая куча");
        return findMinNode()->key;
    }

    Node* findMinNode() const {
        Node* best = nullptr;
        for (Node* r = head_; r; r = r->sibling)
            if (!best || r->key < best->key) best = r;
        return best;
    }

    Node* push(const T& k) {                          // Insert за аморт. O(1)
        Node* x = new Node(k);
        head_ = unionLists(head_, x);
        return x;
    }

    bool pop(T& out) {                                // Extract-Min
        Node* m = findMinNode();
        if (!m) return false;
        out = m->key;
        detachRoot(m);
        return true;
    }

    void decreaseKey(Node* x, const T& k) {
        if (k > x->key) throw std::invalid_argument("новый ключ больше текущего");
        x->key = k;
        for (Node* y = x; y->parent && y->key < y->parent->key; y = y->parent)
            std::swap(y->key, y->parent->key);
    }

    void merge(BinomialHeap& other) {                 // Union за O(log n)
        head_ = unionLists(head_, other.head_);
        other.head_ = nullptr;
    }

    bool contains(const T& k) const { return findNode(head_, k) != nullptr; }

    bool validate() const {
        int lastDegree = -1;
        for (Node* r = head_; r; r = r->sibling) {
            if (r->parent) return false;
            if (r->degree <= lastDegree) return false;   // степени строго возрастают
            lastDegree = r->degree;
            long long size;
            if (!checkNode(r, size)) return false;
        }
        return true;
    }
};

int main() {
    // 1) вставка и извлечение: ключи выходят по возрастанию
    BinomialHeap<int> h;
    for (int v : {7, 3, 9, 1, 8, 2, 5, 0, 6, 4}) h.push(v);
    assert(h.validate());
    std::vector<int> out;
    int x;
    while (h.pop(x)) out.push_back(x);
    assert(std::is_sorted(out.begin(), out.end()));
    assert(out.front() == 0 && out.back() == 9);

    // 2) decrease-key (он же «удаление» через extract-min)
    BinomialHeap<int> g;
    auto n9 = g.push(9);
    g.push(4); g.push(6); g.push(2);
    assert(g.validate());
    g.decreaseKey(n9, -5);
    assert(g.validate());
    int m;
    assert(g.pop(m) && m == -5);
    assert(g.validate());
    assert(!g.contains(9));

    // 3) слияние двух куч
    BinomialHeap<int> a, b;
    for (int v : {1, 3, 5, 7, 9}) a.push(v);
    for (int v : {2, 4, 6, 8, 10}) b.push(v);
    a.merge(b);
    assert(a.validate());
    int prev = std::numeric_limits<int>::min();
    bool ok = true;
    while (a.pop(x)) { if (x < prev) ok = false; prev = x; }
    assert(ok);

    // 4) top() на пустой куче
    BinomialHeap<int> e;
    bool threw = false;
    try { e.top(); } catch (const std::out_of_range&) { threw = true; }
    assert(threw);

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

link вызывается только для деревьев равной степени; в unionLists это обеспечено проверками в строке 9 псевдокода.
detachRoot разворачивает список детей, поэтому unionLists получает список с возрастающими степенями.
decreaseKey требует указателя на узел; получить его можно как результат push либо поиском (contains/findNode, [math]\displaystyle{ O(n) }[/math]). Именно поэтому во многих применениях предпочитают ленивое удаление вместо явного decreaseKey.
decreaseKey обменивает ключи, а не перевешивает узлы: хэндл на предка после операции указывает на узел с другим ключом. Если хэндлы должны сохранять элемент, узлы перевешивают (cut), а не обменивают ключи.
Копирование отключено: корректная копия требует клонирования всех деревьев.

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

Операция	Худший	Амортизированная	Память
Make-Heap	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Find-Min	[math]\displaystyle{ O(\log n) }[/math]; [math]\displaystyle{ O(1) }[/math] при хранении указателя	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Insert	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Extract-Min	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Decrease-Key	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Delete	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Union / Merge	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]

Примечание. Худший случай Insert — [math]\displaystyle{ O(\log n) }[/math] (перенос через все разряды), однако амортизированно вставка стоит [math]\displaystyle{ O(1) }[/math]: серия из [math]\displaystyle{ n }[/math] вставок делает ровно [math]\displaystyle{ n - \operatorname{popcount}(n) }[/math] слияний Link, то есть не больше [math]\displaystyle{ n }[/math]. Это ровно та же амортизация, что у инкремента двоичного счётчика.

Трассировка примера

Вставим по одному ключи [math]\displaystyle{ 1, 2, \dots, 7 }[/math] в пустую кучу и проследим состав леса. Столбец «двоично» — запись числа элементов, «деревья» — степени корней после вставки.

Шаг	Ключ	Двоично	Деревья (степени)	Link на шаге
1	1	0001	{0}	0
2	2	0010	{1}	1
3	3	0011	{0, 1}	0
4	4	0100	{2}	2
5	5	0101	{0, 2}	0
6	6	0110	{1, 2}	1
7	7	0111	{0, 1, 2}	0

Суммарно за 7 вставок выполнено [math]\displaystyle{ 0+1+0+2+0+1+0 = 4 }[/math] слияния, что равно [math]\displaystyle{ 7 - \operatorname{popcount}(7) = 7 - 3 = 4 }[/math]. Минимум всегда в одном из корней; после каждой вставки validate() подтверждает корректность (степени строго возрастают, каждое дерево — [math]\displaystyle{ B_k }[/math]).

Корректность и оценка сложности

Лемма 1 (свойства [math]\displaystyle{ B_k }[/math]). В дереве [math]\displaystyle{ B_k }[/math] ровно [math]\displaystyle{ 2^k }[/math] узлов, высота равна [math]\displaystyle{ k }[/math], степень корня равна [math]\displaystyle{ k }[/math], а число узлов на глубине [math]\displaystyle{ i }[/math] равно [math]\displaystyle{ \binom{k}{i} }[/math].

Доказательство. Индукция по [math]\displaystyle{ k }[/math]. База [math]\displaystyle{ k=0 }[/math]: один узел. Шаг: [math]\displaystyle{ B_k }[/math] состоит из корня и детей [math]\displaystyle{ B_{k-1},\dots,B_0 }[/math], то есть [math]\displaystyle{ \sum_{j=0}^{k-1} 2^j + 1 = 2^k }[/math] узлов. Высота равна [math]\displaystyle{ 1 + (k-1) = k }[/math], степень корня — [math]\displaystyle{ k }[/math]. Число узлов на глубине [math]\displaystyle{ i }[/math] подчиняется [math]\displaystyle{ \binom{k}{i} = \binom{k-1}{i-1} + \binom{k-1}{i} }[/math], что совпадает с рекурсией для суммы детей [math]\displaystyle{ B_{k-1},\dots,B_0 }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Лемма 2 (размер леса). Куча из [math]\displaystyle{ n }[/math] узлов содержит не более [math]\displaystyle{ \lfloor \log_2 n\rfloor + 1 }[/math] деревьев, по одному каждой степени из двоичного разложения [math]\displaystyle{ n }[/math].

Доказательство. Степени корней попарно различны, а дерево степени [math]\displaystyle{ k }[/math] содержит [math]\displaystyle{ 2^k }[/math] узлов. Сумма [math]\displaystyle{ 2^{k} }[/math] по множеству различных [math]\displaystyle{ k }[/math] однозначно задаётся его двоичной записью; значит, [math]\displaystyle{ n }[/math] раскладывается по степеням ровно одним способом. [math]\displaystyle{ \blacksquare }[/math]

Лемма 3 (корректность Union). После Binomial-Heap-Union получается корректная биномиальная куча со всеми элементами исходных.

Доказательство. Merge-Root-Lists не теряет узлов; Binomial-Link лишь перевешивает одно дерево под корень другого, сохраняя min-кучу (родителем выбирается меньший ключ). Консолидация просматривает список слева направо и устраняет любые два соседних дерева равной степени; строка 9 с учётом sibling[next] не допускает ошибочного слияния при трёх деревьях одного размера. По завершении степени попарно различны. [math]\displaystyle{ \blacksquare }[/math]

Теорема 4 (амортизированная стоимость вставки). Серия из [math]\displaystyle{ m }[/math] вставок в пустую биномиальную кучу стоит [math]\displaystyle{ O(m) }[/math].

Доказательство (метод потенциала). Возьмём [math]\displaystyle{ \Phi(H) = }[/math] число деревьев в куче. Вставка создаёт [math]\displaystyle{ B_0 }[/math] и выполняет [math]\displaystyle{ l }[/math] слияний Link, где [math]\displaystyle{ l }[/math] — число «переносов». Фактическая стоимость — [math]\displaystyle{ O(1 + l) }[/math]. Число деревьев меняется на [math]\displaystyle{ +1 - l }[/math], поэтому амортизированная стоимость

[math]\displaystyle{ \hat{c} = O(1 + l) + \Delta\Phi = O(1 + l) + (1 - l) = O(1). }[/math]

Число переносов [math]\displaystyle{ l }[/math] — это длина цепочки единиц в младших разрядах счётчика, зеркально повторяющая двоичный инкремент. Сумма по [math]\displaystyle{ m }[/math] вставкам даёт [math]\displaystyle{ O(m) }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Следствия. Find-Min и один Union — [math]\displaystyle{ O(\log n) }[/math] (длина списка корней). Extract-Min: не более [math]\displaystyle{ \log n }[/math] детей плюс Union — [math]\displaystyle{ O(\log n) }[/math]. Decrease-Key идёт вверх не дальше высоты дерева [math]\displaystyle{ B_k }[/math], то есть [math]\displaystyle{ O(\log n) }[/math].

Сравнение с альтернативами

Структура	Insert	Extract-Min	Decrease-Key	Union	Find-Min
Двоичная куча	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Биномиальная куча	аморт. [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]
Фибоначчиева куча	[math]\displaystyle{ O(1) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	аморт. [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Pairing-куча	[math]\displaystyle{ O(1) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Левосторонняя куча	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]

Те же оценки в наглядной форме — на рис. 8.

Вердикт. Биномиальная куча выигрывает у двоичной слиянием ([math]\displaystyle{ O(\log n) }[/math] против [math]\displaystyle{ \Theta(n) }[/math]) и амортизированной вставкой, но проигрывает фибоначчиевой по decrease-key ([math]\displaystyle{ O(\log n) }[/math] против [math]\displaystyle{ O(1) }[/math]). На практике двоичная куча часто быстрее из-за простоты и локальности; биномиальную выбирают, когда важны частые слияния, либо в учебных и «академических» реализациях.

Рис. 8. Амортизированные сложности. Биномиальная куча ускоряет слияние относительно двоичной; фибоначчиева дополнительно даёт [math]\displaystyle{ O(1) }[/math] на уменьшение ключа.

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

Алгоритм Дейкстры и Прима на разреженных графах. Слияние локальных очередей и быстрое decrease-key критичны; биномиальная куча — первый шаг на пути к фибоначчиевым, ускоряющим Дейкстру до [math]\displaystyle{ O(m + n\log n) }[/math] в теории [1], [4].
Библиотека Boost (C++). boost::heap::binomial_heap даёт готовую реализацию с поддержкой слияния куч и изменения ключа; выбирается, когда нужны объединения очередей [6].
Слияние потоков событий и задач. В дискретно-событийном моделировании и системах планирования нередко удобно вести отдельную очередь на каждый источник событий и объединять их по мере необходимости — это инженерная практика, а не результат отдельной публикации; слияние двух биномиальных куч стоит [math]\displaystyle{ O(\log n) }[/math] [1], поэтому такая схема обходится дёшево.
Параллельные и распределённые вычисления. Частый инженерный шаблон — локальная очередь на каждого воркера и периодическое слияние локальных результатов; в нём решает стоимость слияния, а у биномиальной кучи она логарифмическая [1].
Учебная основа для фибоначчиевых куч. Биномиальная куча показывает ключевые приёмы (лес деревьев, Link, потенциальный анализ), из которых строится фибоначчиева куча, — поэтому она входит в курсы по алгоритмам и в задачи о структурах с decrease-key [1].

Историческая справка

1972. К. Крейн (C. A. Crane) предложил левосторонние кучи — двоичные деревья слияния с логарифмическими границами [9].
1978. Жан Вюйемен ввёл биномиальные кучи как структуру для очередей с приоритетом, поддержку слияния и decrease-key за логарифм [2].
1978. Марк Браун дал реализацию и анализ биномиальных очередей [3].
1986. Фредман, Седжвик, Слейтор и Тарджан предложили pairing-кучи — самонастраивающуюся структуру с амортизированными оценками, близкими к фибоначчиевым [7].
1986. Слейтор и Тарджан предложили скошенные кучи (skew heaps) — более простую самонастраивающуюся альтернативу левосторонним [8].
1987. М. Фредман и Р. Тарджан, опираясь на идею леса деревьев, предложили фибоначчиевы кучи с амортизированным [math]\displaystyle{ O(1) }[/math] на decrease-key [4].
Название «биномиальное» происходит от того, что число узлов дерева [math]\displaystyle{ B_k }[/math] на глубине [math]\displaystyle{ i }[/math] равно биномиальному коэффициенту [math]\displaystyle{ \binom{k}{i} }[/math] [5].

Типичные ошибки и подводные камни

Связывать деревья неравной степени. Link допустим только при degree[y] = degree[z], иначе нарушается форма [math]\displaystyle{ B_k }[/math] и свойство «размер [math]\displaystyle{ =2^k }[/math]».
Забыть обновить degree при Link. Тогда нарушается и форма, и выбор деревьев при слиянии.
Неправильный порядок детей. Корень [math]\displaystyle{ B_k }[/math] должен иметь детей [math]\displaystyle{ B_{k-1},\dots,B_0 }[/math]; при Extract-Min список детей обязательно разворачивается перед Union.
Не обнулить parent у ставших корнями детей. Иначе validate и Find-Min увидят некорректные ссылки.
Путать sibling как «сосед по списку детей» и «следующий корень». Это одно поле, но в разных контекстах оно означает разное — легко ошибиться.
Считать, что две кучи сливаются за [math]\displaystyle{ O(1) }[/math]. Это верно для фибоначчиевых куч; у биномиальной Union стоит [math]\displaystyle{ O(\log n) }[/math].
Ожидать [math]\displaystyle{ O(1) }[/math] в худшем случае от вставки. [math]\displaystyle{ O(1) }[/math] — только амортизированно; отдельная вставка может стоить [math]\displaystyle{ O(\log n) }[/math].
Потерять условие единственности степени. Если после Union остаются два дерева одной степени, Find-Min не сломается сразу, но инвариант (и анализ) рушится; это скрытая ошибка.
Отсутствие явного decrease-key в распространённых библиотеках. Многие контейнеры (в том числе std::priority_queue) его не предоставляют; биномиальная куча — та, где оно есть, но требует указателя на узел.

Задачи для практики

Свойства дерева. Докажите индукцией, что [math]\displaystyle{ B_k }[/math] содержит [math]\displaystyle{ 2^k }[/math] узлов и [math]\displaystyle{ \binom{k}{i} }[/math] узлов на глубине [math]\displaystyle{ i }[/math]. Подсказка: правило Паскаля.
Лес и двоичная запись. Постройте кучу из [math]\displaystyle{ n = 13 }[/math] и из [math]\displaystyle{ n = 50 }[/math] элементов; сколько деревьев и какие степени? Подсказка: двоичное разложение [math]\displaystyle{ n }[/math].
Суммарные слияния. Докажите, что [math]\displaystyle{ n }[/math] вставок в пустую кучу делают ровно [math]\displaystyle{ n - \operatorname{popcount}(n) }[/math] операций Link. Подсказка: двоичный счётчик.
Find-Min за [math]\displaystyle{ O(1) }[/math]. Добавьте указатель на минимальный корень и аккуратно обновляйте его в Insert, Union и Extract-Min. Ограничения: [math]\displaystyle{ n \le 10^6 }[/math].
Слияние двух куч. Реализуйте Union без построения промежуточной кучи, обойдясь одним проходом консолидации. Подсказка: следите за prev, x, next.
Потенциальный анализ. Выведите амортизированную стоимость Extract-Min, выбрав потенциал [math]\displaystyle{ \Phi = }[/math] число деревьев. Подсказка: после удаления минимума число деревьев может вырасти, но не более чем на [math]\displaystyle{ O(\log n) }[/math].
Сравнение с двоичной кучей. На [math]\displaystyle{ 10^5 }[/math] случайных операций (вставки, извлечения, слияния) сравните суммарное время биномиальной и двоичной куч. Подсказка: слияния — сильная сторона биномиальной.
Удаление произвольного узла. Реализуйте Delete(H, x) через Decrease-Key(x, −∞) и Extract-Min; докажите, что стоимость [math]\displaystyle{ O(\log n) }[/math].

Связанные темы

Двоичная куча — базовый частный случай; быстрее на практике, но не умеет быстро сливаться.
Фибоначчиева куча — амортизированное [math]\displaystyle{ O(1) }[/math] на decrease-key и слияние.
Очередь с приоритетом — абстрактный тип данных.
Алгоритм Дейкстры — основной потребитель слияний и decrease-key.
Алгоритм Прима — минимальное остовное дерево.
Амортизационный анализ — метод потенциала и двоичный счётчик.
Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 2nd ed. — MIT Press, 2001. — Гл. 19 «Binomial Heaps», гл. 20 «Fibonacci Heaps». (В 3-м изд. 2009 г. биномиальные кучи вынесены в задачу 19-2.)
Vuillemin J. A Data Structure for Manipulating Priority Queues // Communications of the ACM. — 1978. — Vol. 21, No. 4. — P. 309–315.
Brown M. R. Implementation and Analysis of Binomial Queue Algorithms // SIAM Journal on Computing. — 1978. — Vol. 7, No. 3. — P. 298–319.
Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms // Journal of the ACM. — 1987. — Vol. 34, No. 3. — P. 596–615 (проверено).
Wikipedia: Binomial heap. URL: https://en.wikipedia.org/wiki/Binomial_heap.
Boost.Heap: binomial_heap. URL: https://www.boost.org/doc/libs/release/doc/html/heap.html.
Fredman M. L., Sedgewick R., Sleator D. D., Tarjan R. E. The Pairing Heap: A New Form of Self-Adjusting Heap // Algorithmica. — 1986. — Vol. 1, No. 1. — P. 111–129.
Sleator D. D., Tarjan R. E. Self-Adjusting Heaps // SIAM Journal on Computing. — 1986. — Vol. 15, No. 1. — P. 52–69.
Crane C. A. Linear Lists and Priority Queues as Balanced Binary Trees. — Stanford University, Computer Science Department. — Technical Report STAN-CS-72-259, 1972.

Поиск

Навигация

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

Содержание

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: слияние двух деревьев (Link)

Операция: объединение куч (Union)

Операция: вставка (Insert)

Операция: поиск минимума (Find-Min)

Операция: извлечение минимума (Extract-Min)

Операция: уменьшение ключа (Decrease-Key)

Операция: создание кучи (Make-Heap)

Реализация структуры на C++

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

Трассировка примера

Корректность и оценка сложности

Сравнение с альтернативами

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

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Связанные темы

Источники