333
правки
Изменения
→extractMin
Рассмотрим пошагово алгоритм:
* Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево <tex>B_k</tex>. Время работы этого шага алгоритма <tex>O\Theta(\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> за <tex>\Omega(\log(n))</tex>.
