Изменения
Нет описания правки
next_x = sibling[x]
</code>
=== Inset ===
Приведенная ниже процедура вставляет узел х в биномиальную пирамиду Н (предполагается, что для х уже выделена память и поле key[x] уже заполнено):
<code>
Binomial_Heap_Insert(H, x)
H' = Make_Binpmial_Heap
p[x] = NIL
child[x] = NIL
sibling[x] = NIL
degree[x] = 0
head[H'] = x
H = Binomial_Heap_Union(H, H')
</code>
Процедура просто создает биномиальную пирамиду H' с одним узлом за время О(1) и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время О(lg(n)).
=== Extract_Min ===
Приведенная ниже процедура извлекает узел с минимальным ключок из биномиальной кучи и возвращает указатель на извлеченный узел:
<code>
Binomial_Heap_Extract_Min(H)
поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н
H' = Make_Binomial_Heap()
Обращение порядка связанного списка дочерних узлов х,
установка поля р каждого дочернего узла Н равным NIL
присвоение указателю head[H'] адреса заголовка
получающегося списка
H = Binomial_Heap_Union(H, H')
return x
</code>
Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи.
Все действия выполняются за время O(lgn), так что общее время работы процедуры есть O(lgn)
