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

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

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

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

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

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

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

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

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

См. такжеПравить