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

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

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

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

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

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

Таким образом, биномиальные кучи эффективны для представления приоритетных очередей с возможностью объединения.

См. также

  • Двоичная куча
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home