Изменения
→"Уплотнение" (Consolidate)
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.
Затем происходит [http://neerc.ifmo.ru/mediawiki/index.php/Биномиальная_куча#Union процесс, аналогичный слиянию биномиальных куч: ] добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex> . Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.
Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:
