Биномиальная куча () — структура данных, реализующая абстрактный тип данных «очередь с приоритетом».
Конструируется как набор биномиальных деревьев — объектов, задаваемых рекуррентно следующим образом: биномиальное дерево нулевого ранга состоит из одной вершины; биномиальное дерево ранга представляет собой вершину и детей, ранг которых последовательно уменьшается с до 0.
Таким образом, биномиальное дерево ранга содержит вершин и имеет вершин на глубине , в честь чего оно и получило своё название.
Из двух деревьев ранга можно образовать одно ранга путём подвешивания одного из них к корню другого в качестве -ой ветви.
Биномиальная куча обладает двумя свойствами: ключ каждой вершины не меньше ключа её родителя; все биномиальные деревья имеют разный размер.
Из этих свойств вытекают два следствия. Во-первых, корень каждого из деревьев имеет наименьший ключ среди его вершин. Во-вторых, суммарное количество вершин в биномиальной куче однозначно определяет размеры входящих в неё деревьев. Например, биномиальная куча с вершинами состоит из трёх деревьев высотой 3, 2 и 0 и имеющих, соответственно, 8, 4 и 1 элементов.
Следующие операции выполняются за время , где — число вершин: вставка нового элемента (амортизационная сложность — ), нахождение элемента с минимальным ключом, удаление элемента с минимальным ключом, уменьшение значения ключа данного элемента, удаление данного элемента, объединение двух куч.
Таким образом, биномиальная куча является сливаемой кучей, то есть кроме стандартных операций очереди с приоритетом (добавления, удаления, извлечения минимума, изменения ключей) предоставляет дополнительную операцию слияния двух куч.
Примечания
Категория:Кучи (структуры данных)