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

Биномиальная куча (англ. binomial heap) — структура данных, реализующая абстрактный тип данных «очередь с приоритетом».

Конструируется как набор биномиальных деревьев — объектов, задаваемых рекуррентно следующим образом:^[1]

• биномиальное дерево нулевого ранга состоит из одной вершины;
• биномиальное дерево ранга ${\displaystyle k}$ представляет собой вершину и ${\displaystyle k}$ детей, ранг которых последовательно уменьшается с ${\displaystyle k-1}$ до 0.

Таким образом, биномиальное дерево ранга ${\displaystyle k}$ содержит ${\displaystyle 2^{k}}$ вершин и имеет ${\displaystyle C_{k}^{d}}$ вершин на глубине ${\displaystyle d}$, в честь чего оно и получило своё название.

Из двух деревьев ранга ${\displaystyle k-1}$ можно образовать одно ранга ${\displaystyle k}$ путём подвешивания одного из них к корню другого в качестве ${\displaystyle k}$-ой ветви.

Биномиальная куча обладает двумя свойствами:

• ключ каждой вершины не меньше ключа её родителя;
• все биномиальные деревья имеют разный размер.

Из этих свойств вытекают два следствия. Во-первых, корень каждого из деревьев имеет наименьший ключ среди его вершин. Во-вторых, суммарное количество вершин в биномиальной куче однозначно определяет размеры входящих в неё деревьев. Например, биномиальная куча с ${\displaystyle 13=2^{3}+2^{2}+2^{0}}$ вершинами состоит из трёх деревьев высотой 3, 2 и 0 и имеющих, соответственно, 8, 4 и 1 элементов.

Следующие операции выполняются за время ${\displaystyle O(\log n)}$, где ${\displaystyle n}$ — число вершин:

• вставка нового элемента (амортизационная сложность — ${\displaystyle O(1)}$),
• нахождение элемента с минимальным ключом,
• удаление элемента с минимальным ключом,
• уменьшение значения ключа данного элемента,
• удаление данного элемента,
• объединение двух куч.

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