Изменения

Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура <tex> consolidate </tex>. Возьмем указатель на <tex> H.min </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D(n) </tex>, где <tex> D(n) </tex> {{---}} максимальная степень вершины в куче) объединим с корневым списком. Теперь вызываем процедуру <tex> consolidate </tex>. После этой операции в списке корней остается не более чем <tex> D(n) + 1</tex> узлов, среди которых нужно найти минимальный. Итоговая асимптотика операции <tex>extraxtMin</tex>, учитывая и вспомогательную функцию <tex> consolidate </tex>, время работы которой доказывается ниже, равно: <tex> O(1)+O(D(n))+O(D(n))=O(D(n)) </tex>. Но по По доказанной выше [[#Лемма4|лемме]] это <tex>O(D(n)) = O(\log(n))</tex>.