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