403
правки
Изменения
→consolidate
==== consolidate ====
Данная процедура принимает кучу, и делает из нее кучупреобразует ее таким образом, что в корневом списке которой остается не более <tex> D(n) + 1</tex> вершин.
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> {{---}} максимальная степень вершины в текущем корневом списке.
Затем происходит [[Биномиальная_куча#Union | процесс, аналогичный слиянию биномиальных куч ]]: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex>. Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.
Учетная стоимость <tex> consolidate </tex> равна <tex> O(D(n)) </tex>. Докажем это:
