Изменения
Нет описания правки
== Extract_min ==
Первая рассматриваемая операция, в ходе которой меняется структура кучи. Здесь используется вспомогательная процедура Consolidate("уплотнение" кучи). Возьмем указатель на <tex> min[H] </tex>, удалим эту вершину. Ее поддеревья (их не более, чем <tex> D[H] </tex>) все положим в корневой список. Теперь вызываем процедуру <tex> Consolidate </tex>.
=== Consolidate ===
Данная процедура принимает кучу, и делает из нее кучу, в корневом списке которой <tex> O(logND[H}) </tex> вершин.
Для этого возьмем массив списков указателей на корни деревьев <tex> A[0..D[H]] </tex>, где <tex> D[H] </tex> - максимальная степень вершины в текущем корневом списке. Далее мы увидим, что <tex> D[H] = O(logN) </tex>.
Затем происходит процесс, аналогичный слиянию биномиальных куч: добавляем поочередно каждый корень, смотря на его степень. Пусть она равна <tex> d </tex> Если в соответствующей ячейке A еще нету вершины, записываем текущую вершину туда. Иначе подвешиваем одно дерево к другому, и пытаемся также добавить дерево, степень корня которого уже равна <tex> d + 1 </tex>. Продолжаем, пока не найдем свободную ячейку.
Учетная стоимость <tex> Consolidate </tex> равна <tex> O(D[H]) </tex>. Докажем это:
Пусть изначально в корневом списке было <tex> r </tex> вершин. Тогда в ходе операции <tex> Consolidate </tex> мы сделали <tex> O(r) </tex> слияний деревьев. Но эти <tex> O(r) </tex> слияний скомпенсируются уменьшением потенциала <tex> t_i + \Phi_i - \Phi_{i - 1} = r + (O(D[H]) - r) = O(D[H]) </tex>. Остальных действий будет также <tex> O(D[H]) </tex>. Таким образом, учетная стоимость <tex> Consolidate: \, O(D[H]) </tex>.
== Decrease_key ==
Основная идея: хотим, чтобы учетная стоимость данной операции была <tex> O(1) </tex>.
- Хотим, чтобы вершина не всплывала до корня
