дерево Uk получается из двух экземпляров деревьев Uk-i, если корень одного добавить к числу детей корня другого. (Таким образом, дети корня в дереве Uk являются вершинами деревьев Uo, U\,..., Uk-i-) Лемма 20.1 остается верной и для неупорядоченных биномиальных деревьев (надо только исключить в свойстве 4 упоминание о порядке).

В частности, степени всех вершин в фибоначчиевой куче размера га, составленной из неупорядоченных биномиальных деревьев, ограничены величиной D(n) = lgra.

В отличие от биномиальных куч, теперь среди входящих в кучу деревьев может быть несколько деревьев с одной и той же степенью корня. Их «консолидация» откладывается до момента выполнения операции Extract-Min, когда деревья с корнями одинаковой степени объединяются.

Создание новой фибоначчиевой кучи

Процедура Make-Fib-Heap создаёт и возвращает объект Н, для которого га[Я] = 0 и тгп[Н] = nil: корневой список этой кучи пуст. При этом t(H) = 0 и т(Н) = 0, так что потенциал кучи равен 0, а суммарный потенциал не меняется. Учётная стоимость операции Make-Fib-Heap равна её фактической стоимости 0(1).

Добавление вершины

Следующая процедура добавляет вершину ж в фибоначчиеву кучу Н (предполагаем, что вершина х уже размещена в памяти и поле ключа кеу[х] заполнено).

Fib-Heap-Insert (Я, ж)

1degree[x] <- О

2р[х] <- nil

3child[x] <- nil

4left[x] <- x

5right[x] <- x

6mark[x] <- false

7соединить полученный корневой список

10 га[Я] <- га[Я] + 1

Строки 1-6 формируют циклический список из единственной вершины ж, и в строке 7 эта вершина добавляется (за время 0(1)) к корневому списку кучи Я, в которой появляется новое одно-

Рис. 21.2 Добавление вершины, (а) Фибоначчиева куча Н. (б) Та же куча Н после добавления вершины с ключом 21. (Эту вершину сделали одноэлементным деревом, а затем добавили в корневой список слева от минимальной вершины, которая в данном случае осталась минимальной.)

элементное дерево. Вершина х не имеет потомков и не отмечена. В строках 8-9 обновляется (если необходимо) указатель на минимальную вершину. Наконец, строка 10 увеличивает значение п[Н].

На рис. 21.2 показано добавление вершины с ключом 21 в фибо-наччиеву кучу рис. 21.1.

В отличие от процедуры Binomial-Heap-Insert, процедура Fib-Heap-Insert не пытается соединять деревья с одинаковой степенью вершины. Если выполнить подряд к операций Fib-Heap-Insert, то в корневой список будут добавлены к деревьев по одной вершине в каждом.

Найдём учётную стоимость операции Fib-Heap-Insert. Её фактическая стоимость есть- 0(1), и увеличение потенциала также есть 0(1) (в корневой список добавилась одна вершина). Таким образом, учётная стоимость составляет 0(1).

Поиск минимальной вершины

Указатель на неё хранится в тгп[Н], так что фактическая стоимость этой операции есть 0(1). Потенциал при этом не меняется, так что и учётная стоимость есть 0(1).

Соединение двух фибоначчиевых куч

Следующая процедура из двух фибоначчиевых куч Н\ и Н2, делает одну (при этом исходные кучи исчезают).

Fib-Heap-Union(#i, Я2)

1Я <- Make-Fib-Heap()

2min[H] <- min[Hi]

3соединить корневой список Я2 с корневым списком Я

4if (mm[ffi] = nil) or (тт[Я2] / nil and тт[Я2] < min[ffi])

5then min[H] <- тт[Я2]

6п[Я] <- n[ffi] + п[Я2]

7освободить память, занятую под заголовки объектов Н\ и Я2

8return Я

Строки 1-3 объединяют корневые списки куч Н\ и Я2 в корневой список новой кучи Я. Строки 2, 4 и 5 заполняют тт[Я], а строка 6 устанавливает п[Н] равным суммарному количеству вершин. Объекты Н\ и Я2 освобождаются в строке 7, а строка 8 возвращает результирующую фибоначчиеву кучу Я. Отметим, что (как и в процедуре Fib-Heap-Insert) соединения деревьев не происходит. Потенциал не меняется (общее число вершин в корневых списках и общее число помеченных вершин остаётся тем же). Поэтому учётная стоимость операции Fib-Heap-Union равна её фактической стоимости, т.е. 0(1).

Изъятие минимальной вершины

Именно при этой операции происходит преобразование структуры кучи (разные деревья соединяются в одно), поэтому она существенно сложнее предыдущих операций этого раздела. План действий таков: после изъятия минимальной вершины то дерево, где она была корнем, рассыпается в набор своих поддеревьев, которые добавляются к корневому списку. Затем запускается процедура Consolidate, соединяющая деревья, после чего в корневом списке остаётся не более одного дерева каждой степени.

Мы считаем, что при удалении вершины из связанного списка (строка 6) поля left и right этой вершины остаются неизменными (но поля её соседей, которые указывали на эту вершину, обновляются).