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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример биномиальной кучи, содержащий элементы с ключами от 1 до 13

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

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

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

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

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

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

См. также[править | править исходный текст]