Изменения
Нет описания правки
|definition=
'''Биномиальная куча ''' представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:
*Каждое биномиальное дерево в пирамиде куче подчиняется свойству '''[[Двоичная куча|неубывающей пирамидыкучи]]''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей пирамиды кучи дерево).
*Для любого неотрицательного целого <tex>k</tex> найдется не более одного биномиального дерева, чей корень имеет степень <tex>k</tex>.}}
== Представление биномиальных куч ==
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:
*<tex>key</tex> {{---}} ключ (вес) элемента;
*<tex>parent</tex> {{---}} указатель на родителя узла;
*<tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
Корни деревьев, их которых состоит пирамидакуча, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в возрастающем порядке.
Доступ к куче осуществляется ссылкой на первый корень в списке корней.
== Операции над биномиальными кучами==
Рассмотрим операции, которые можно производить с биномиальной пирамидойкучей. Время работы указано в таблице:
{| border="1"
|insert
|<tex>\Theta(\log(n))</tex>
|}
Обозначим нашу кучу за <tex>H</tex>. То пусть <tex>H.head</tex> {{---}} указатель на корень биномиального дерева минимального порядка этой кучи. Изначально <tex>H.head = null</tex>, то есть пирамида куча не содержит элементов.
=== getMinimum ===
=== insert ===
Чтобы добавить новый элемент в биномиальную кучу нужно создать биномиальную пирамиду кучу <tex>H'</tex> с единственным узлом, содержащим этот элемент, за время <tex>O(1)</tex> и объединить ее с биномиальной пирамидой кучей <tex>H</tex> за <tex>O(\log(n))</tex>, так как в данном случае куча <tex>H'</tex> содержит лишь одно дерево.
=== extractMin ===
