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

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