333
правки
Изменения
Нет описания правки
=== getMinimum ===
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\inftyinf</tex>, нет).
Так как корней в этом списке не более <tex>\lfloor \log n \rfloor + 1</tex>, то операция выполняется за <tex>O(\log n)</tex>.
<code>
'''BinomialHeap''' merge(H1 : '''BinomialHeap''', H2 : '''BinomialHeap''')
'''if''' H1 == ''null ''
'''return''' H2
'''if''' H2 == ''null ''
'''return''' H1
H.head = ''null '' <font color = "green"> // H {{---}} результат слияния </font>
curH = H.head <font color = "green"> // слияние корневых списков </font>
curH1 = H1.head
curH2 = H2.head
'''while''' curH1 != ''null '' '''and''' curH2 != ''null ''
'''if''' curH1.degree < curH2.degree
curH.sibling = curH1
curH = curH2
curH2 = curH2.sibling
'''if''' curH1 == ''null '' '''while''' curH2 != ''null ''
curH.sibling = curH2
curH2 = curH2.sibling
'''else'''
'''while''' curH1 != ''null ''
curH.sibling = curH1
curH1 = curH1.sibling
curH = H.head <font color = "green"> // объединение деревьев одной степени </font>
'''while''' curH.sibling != ''null ''
'''if''' curH.degree == curH.sibling.degree
p[curH] = curH.sibling
<code>
'''Node''' extractMin(H : '''BinomialHeap''') <font color = "green">//поиск корня х с минимальным значением ключа в списке корней Н: </font>
min = ''inf'' x = ''null'' xBefore = ''null''
curx = H.head
curxBefore = ''null'' '''while''' curx != ''null ''
'''if''' curx.key < min <font color = "green"> // релаксируем текущий минимум </font>
min = curx.key
curxBefore = curx
curx = curx.sibling
'''if''' xBefore == ''null '' <font color = "green"> //удаление найденного корня x из списка корней деревьев кучи</font>
H.head = x.sibling
'''else'''
xBefore.sibling = x.sibling
H' = ''null '' <font color = "green">//построение кучи детей вершины x, при этом изменяем предка соответствующего ребенка на ''null'':</font>
curx = x.child
H'.head = x.child
'''while''' curx != ''null '' p[curx] = ''null '' <font color = "green">// меняем указатель на родителя узла curx </font>
curx = curx.sibling <font color = "green">// переход к следующему ребенку </font>
H = merge(H, H') <font color = "green">// слияние нашего дерева с деревом H' </font>
y = x
z = p[y]
'''while''' z != ''null '' '''and''' key[y] < key[z] <font color = "green">// поднимаем x с новым ключом k, пока это значение меньше значения в родительской вершине </font>
swap(key[y], key[z])
y = z
<code>
'''function''' delete(H : '''BinomialHeap''', x : '''Node''')
decreaseKey(H, x, -''inf'') <font color = "green">// уменьшение ключа до минимально возможного значения </font>
extractMin(H) <font color = "green">// удаление "всплывшего" элемента </font>
</code>
