Изменения
Нет описания правки
Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи.
Все действия выполняются за время O(lgn), так что общее время работы процедуры есть O(lgn)
=== Decrease_Key ===
Следующая процедура уменьшает ключ элемента х биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время O(lgn), поскольку глубина вершины х есть O(lgn) (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
<code>
Binomial_Heap_Decrease_Key(H, x, k)
if k > key[x] then
return
key[x] = k
y = x
z = p[y]
while (z <tex>\ne</tex> NIL and key[y] < key[z]) do
swap(key[y], key[z])
y = z
z = p[y]
</code>
=== Delete ===
Удаление ключа сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения, а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время O(lgn).
<code>
Binomial_Heap_Delete(H, x)
Binomial_Heap_Decrease_Key(H, x, -<tex>\infty</tex>)
Binomial_Heap_Extract_Min(H)
</code>
