251
правка
Изменения
м
Нет описания правки
{{Определение
|definition =
'''Биномиальное дерево <tex>B_k</tex>'''(англ. ''binomial heaptree'') {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{---}} дерево, состоящее из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.
}}
{{Определение
|definition=
'''Биномиальная куча ''' (англ. ''binomial heap'') представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:*Каждое каждое биномиальное дерево в куче подчиняется свойству '''[[Двоичная куча|неубывающей кучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей кучи дерево).,*Для для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <tex>k</tex>.}}
== Представление биномиальных куч ==
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей:
*<tex>key</tex> {{---}} ключ (вес) элемента;,*<tex>parent</tex> {{---}} указатель на родителя узла;,*<tex>child</tex> {{---}} указатель на левого ребенка узла;,*<tex>sibling</tex> {{---}} указатель на правого брата узла;,
*<tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
! Операция || Время работы
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm \mathtt{insert}</tex>||<tex>O(\log n)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm \mathtt{getMinimum}</tex>||<tex>O(\log n)</tex>
|-align="center" bgcolor=#FFFFFF
||<tex>\mathrm \mathtt{extractMin}</tex>||<tex>\Theta(\log n)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm \mathtt{merge}</tex>||<tex>\Omega(\log n)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm \mathtt{decreaseKey}</tex>||<tex>\Theta(\log n)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm \mathtt{delete}</tex>||<tex>\Theta(\log n)</tex>
|}
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть куча не содержит элементов.
=== Конфлюэнтная персистентность ===
Благодаря поддержке операции <math>\mathrm {Mergemerge}</math> биномиальная куча является конфлюэнтной структурой данных, что позволяет получать новую версию путём сливания старых.
