333
правки
Изменения
→extractMin
* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <tex>B_k</tex>. Время работы этого шага алгоритма <tex>O(\log n)</tex>.
* Удаляем дерево <tex>B_k</tex> из кучи <tex>H</tex>. Иными словами удаляем его корень из списка корней кучи. Это можно сделать за время <tex>O(1)</tex>.
* Переберем Построим новую кучу <tex>H'</tex> из детей найденного корня. Для этого переберем детей удаленного корня, причем в ходе перебора устанавливаем указатель на предка равным <tex>null</tex>. Для каждого ребенка создадим новое дерево После этого сливаем построенную кучу <tex>H'</tex>, которое сливаем с кучей c <tex>H</tex> за O<tex>\Omega(\log (n))</tex>.
Процедура выполняется за время <tex>O\Theta(\log (n))</tex>, поскольку всего в списке <tex>O\Theta(\log (n))</tex> корней биномиальных деревьев. И всего у найденного дерева <tex> k </tex> порядка(с минимальным значением ключа) ровно <tex> k </tex> детей, то сложность перебора этих детей будет тоже <tex>O\Theta(\log (n))</tex>. Таким образом операция А процесс слияния выполняется за <tex>O\Omega(\log (n) + O)</tex>. Таким образом операция выполняется <tex>\Theta(\log (n) = O(\log n)</tex>.
<code>
x.next.prev = x.prev;
//построение кучи детей вершины x, при этом будем изменять изменяем предка соответствующего ребенка на null:
H' = null;
curx = x.child;
