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