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

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

Пример биномиальной кучи, содержащий элементы с ключами от 1 до 13

Описание

Биномиальная куча представляет собой набор биномиальных деревьев — объектов, задаваемых рекуррентно следующим образом:

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

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

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

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

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

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

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

• Вставка нового элемента (амортизированное $O(1)$)
• Нахождение элемента с минимальным ключом
• Удаление элемента с минимальным ключом
• Уменьшение значения ключа данного элемента
• Удаление данного элемента
• Объединение двух куч.

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

См. также

• Двоичная куча
• Фибоначчиева куча