Изменения
→Операции над биномиальными пирамидами
Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.
{| border="1"
|Make_HeapmakeHeap
|<tex>\Theta(1)</tex>
|-
|Insertinsert
|<tex>O(\log(n))</tex>
|-
|MinimumgetMinimum
|<tex>O(\log(n))</tex>
|-
|Extract_MinextractMin
|<tex>\Theta(\log(n))</tex>
|-
|Unionmerge
|<tex>\Omega(\log(n))</tex>
|-
|Decrease_KeydecreaseKey
|<tex>\Theta(\log(n))</tex>
|-
|Deletedelete
|<tex>\Theta(\log(n))</tex>
|}
=== Make_Heap makeHeap ===Для создания пустой биномиальной приамиды пирамиды процедура Make_Binomial_Heap makeBinomialHeap просто выделяет память и возвращает объект H, где head[H] = nilnull, то есть пирамида не содержит элементов.
=== Minimum getMinimum ===
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).
[[Файл:Example2.jpg|300px]]
=== Union merge ===
Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
[[Файл:Example3.jpg|300]]
Пример пирамиды до Union merge и после:
[[Файл:Example5.jpg]]
=== Insert insert ===
Необходимо просто создать биномиальную пирамиду <tex>H'</tex> с одним узлом за время <tex>O(1)</tex> и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время <tex>O(\log(n))</tex>.
=== Extract_Min extractMin ===
Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел:
<code>
поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н
H' = Make_Binomial_Heap()
Все действия выполняются за время <tex>O(\log n)</tex>, так что общее время работы процедуры есть <tex>O(\log n)</tex>.
=== Decrease_Key decreaseKey ===
Следующая процедура уменьшает ключ элемента x биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время <tex>O(\log n)</tex>, поскольку глубина вершины x есть <tex>O(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
[[Файл:Example6.jpg|600px]]
=== Delete delete ===
Удаление ключа сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения, а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>O(\log n)</tex>.
