се этих преобразований вершина w остаётся потомком вершины ж.

Инвариант цикла while (строки 6-12) таков: «d = degree[x]; осталось добавить дерево с корнем в ж к множеству, представленному массивом А». Если при этом A[d] = nil, то мы выполняем эту операцию (добавление) в строке 13. Если же A[d] ф nil, то мы имеем два дерева степени d с корнями в ж и у = A[d], и в строках 8-10 соединяем их в одно дерево с корнем в ж (одновременно очищая ячейку A[d] и сохраняя инвариант).

Различные стадии этого процесса показаны на рис. 21.3.

После этого остаётся преобразовать массив А в корневой список: в строке 14 мы создаём пустой список, а в цикле в строках 15-19 добавляем в него по очереди все вершины, имеющиеся в массиве А. Результат показан на рис. 21.3м.

На этом процесс уплотнения заканчивается, и управление возвращается в процедуру Fib-Heap-Extract-Min, которая уменьшает п[Н] на 1 и возвращает указатель на изъятую вершину z (строки 11-12).

Заметим, что если перед выполнением операции Fib-Heap-Extract-Min все деревья в Н были неупорядоченными биномиальными деревьями, то и после выполнения операции Н будет состоять из неупорядоченных биномиальных деревьев. В самом деле, соединение двух неупорядоченных биномиальных деревьев с одина-

ковыми степенями корня (процедура Fib-Heap-Link) даёт (неупорядоченное) биномиальное дерево (степень его корня на единицу больше).

Нам осталось показать, что учётная стоимость изъятия минимальной вершины из га-элементной фибоначчиевой кучи есть 0(D(n)). Посмотрим, какие операции нам пришлось выполнить. Прежде всего нужно 0(D(n)) действий, чтобы поместить всех потомков удаляемой вершины z в корневой список. Начальный и конечный этапы работы процедуры Consolidate (строки 1-2 и 1519) также требует времени 0(D(n)). Остаётся учесть вклад цикла for, расположенного в строках 3-13. Это число оценивается сверху как 0(D(n)) (размер массива А) плюс константа, умноженная на число обращений к процедуре Fib-Heap-Link. Но при каждом таком обращении два дерева сливаются, что приводит в итоге к уменьшению длины корневого списка на 1 и к уменьшению потенциала по крайней мере на 1 (число отмеченных вершин может уменьшиться, но не увеличиться). Так что умножив потенциал на подходящую константу, мы можем считать, что учётная стоимость операции удаления есть 0(D(n)).

Другими словами, операции связывания деревьев одинаковой степени (которых может быть много, если корневой список длинный) оплачиваются как раз за счёт уменьшения длины корневого списка!

Упражнения

21.2-1 Нарисуйте фибоначчиеву кучу, которая получится в результате изъятия минимальной вершины (с помощью процедуры Fib-Heap-Extract-Min) из кучи рис. 21.3м.

21.2-2 Докажите, что лемма 20.1 остаётся верной для неупорядоченных биномиальных деревьев, если свойство 4 заменить на свойство 4: корень неупорядоченного биномиального дерева Uk имеет степень к, которая является максимальной степенью вершины в дереве; дети корня являются вершинами деревьев Со, U\,..., Uk-i (в некотором порядке).

21.2-3 Покажите, что если выполняются лишь операции, описанные в разделе 21.2, то в куче с га вершинами все вершины имеют степень не больше [lg raj.

21.2-4 Профессор придумал новую структуру данных, основанную на фибоначчиевых кучах: операции выполняются как описано в разделе 21.2, но только после добавления вершины и соединения двух куч сразу же производится уплотнение корневого списка. Каково время выполнения различных операций над такими кучами в

худшем случае? Будет ли такая структура данных чем-то новым?

21.2-5 Будем считать, что ключи можно только сравнивать (их внутренняя структура нам недоступна). Можно ли тогда реализовать операции над сливаемыми кучами так, чтобы каждая из них имела учётную стоимость 0(1)? (Указание: используйте оценки для времени сортировки.)

В этом разделе мы покажем, как реализовать операцию уменьшения ключа заданной вершины с учётной стоимостью 0(1), а также операцию удаления вершины из фибоначчиевой кучи с учётной стоимостью 0(D(n)) (где га - число вершин в куче), a D(n) - оценка для максимальной степени вершины.

После этих операций входящие в кучу деревья перестают быть биномиальными, но не слишком далеко отклоняются от них, так что максимальная степень вершины остаётся равной О (lg га). Таким образом, операции Fib-Heap-Extract-Min и Fib-Heap-Delete имеют учётную стоимость О (lgra).

Уменьшение ключа

В следующей процедуре уменьшения ключа (Fib-Heap-Decrease-Key) мы предполагаем, что после изъятия вершины из списка ссылка на вершину-ребёнка не меняется (так что процедура Сит вырезает целое поддерево, см. ниже)

Fib-Heap-Decrease-Key (Я, ж, к)

1if к > кеу[х]

2then error «новое значение ключа больше старого»

3кеу[х] <- к

4у <- р[х]

5if у ф nil and кеу[х] < кеу[у]

6then Сит(Я, ж, у)

21.3. Уменьшение ключа и удаление вершины

7 8 9

if кеу[х] < кеу[тгп[Н]] then тгп[Н] <- ж