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

Как и динамические таблицы раздела 18.4, фибоначчиевы кучи являются примером структуры данных, разработанной с учётом амортизационного анализа (см. гл. 18, особенно разд. 18.3 о методе потенциала).

Мы предполагаем, что вы прочли предыдущую главу (о биномиальных кучах). Там была приведена таблица (рис. 20.1), где указаны оценки времени работы различных операций с биномиальными и фибоначчиевыми кучами.

Как и биномиальные кучи, фибоначчиевы кучи не обеспечивают эффективного выполнения поиска (Search). Поэтому передавая вершину в качестве параметра, мы указываем не ключ вершины, а указатель на неё.

В разделе 21.1 мы определим фибоначчиевы кучи, обсудим их представление в программе и введём потенциальную функцию. В разделе 21.2 мы покажем, как реализовать операции, присущие сливаемым кучам, с оценками учётной стоимости, указанными в таблице (рис. 20.1). Оставшиеся две операции (Decrease-Key и Delete) описаны в разделе 21.3. Наконец, в разделе 21.4 мы доказываем лемму, использованную при анализе построенных процеДУР-

21.1. Строение фибоначчиевой кучи

При использовании фибоначчиевых куч для хранения набора множеств каждое множество занимает несколько деревьев, корни которых связаны в список. Такой конгломерат мы будем называть фибоначчиевой кучей (Fibonacci heap). Таким образом, каждая фи-боначчиева куча состоит из нескольких деревьев; для каждого хранимого множества отводится своя куча.

В каждом из деревьев, входящих в кучу, выполнено такое свойство: ключ каждой вершины не больше ключей её детей. Деревья, однако, более не обязаны быть биномиальными. Пример фибоначчиевой кучи приведён на рис. 21.1а.

В биномиальных деревьях на детях любой вершины фиксирован порядок; в фибоначчиевых деревьях такого порядка нет (дети любой вершины связаны в круговой двусторонний список, но порядок в нём несуществен). Как показано на рис. 21.16, каждая вершина х содержит указатель р[х] на своего родителя и указатель child[x] на какого-нибудь из своих детей.

Дети вершины х связаны в двусторонний циклический список, называемый списком детей (child list) вершины х. Каждая верши-

Рис. 21.1 (а) Фибоначчиева куча, содержащая 5 деревьев и 14 вершин. Пунктирной линией показан корневой список. Минимальная вершина содержит ключ 3. Три отмеченные вершины выделены чёрным цветом. Потенциал этой кучи равен 5 + 2-3 = 11. (б) Та же куча вместе со стрелками, показывающими значения полей р (стрелки вверх), child (стрелки вниз) и left и right (стрелки в стороны). На остальных рисунках этой главы такие стрелки опущены, так как они восстанавливаются однозначно.

на у этого списка имеет поля left[y] и right[y], указывающие на её соседей в списке (левого и правого). Если вершина у является единственным ребёнком своего родителя, то left[y] = right[y] = у.

Двусторонние циклические списки (см. разд. 11.2) удобны по двум причинам. Во-первых, из такого списка можно удалить любую вершину за время 0(1). Во-вторых, два таких списка можно соединить в один за время 0(1).

Помимо указанной информации, каждая вершина имеет поле degree[x], где хранится её степень (число детей), а также поле тагк[х]. В этом поле хранится булевское значение. Смысл его таков: тагк[х] истинно, если вершина х потеряла ребёнка после того, как она в последний раз сделалась чьим-либо потомком. Мы объясним позже, как и когда это поле используется.

Корни деревьев, составляющих фибоначчиеву кучу, связаны с помощью указателей left и right в двусторонний циклический список, называемый корневым списком (root list).

Доступ к фибоначчиевой куче Н осуществляется с помощью атрибута min[H], который указывает на вершину корневого списка с минимальным ключом. Эта вершина называется минимальной вершиной (minimum node) кучи. Её ключ будет минимальным ключом в куче, поскольку минимальный ключ фибоначчиева дерева находится в его корне. Порядок вершин в корневом списке значения

не имеет. Если фибоначчиева куча Н пуста, то тгп[Н] = nil. Наконец, атрибут п[Н] содержит число вершин в куче Н.

Потенциал

При анализе учётной стоимости операций мы используем метод потенциала (раздел 18.3). Пусть t(H) - число деревьев в корневом списке кучи Н, а т(Н) - количество отмеченных вершин. Потенциал определяется формулой

Ф(Н) = Ь{Н) + 2т{Н).(21.1)

Например, потенциал кучи рис. 21.1 равен 5 + 2-3 = 11. В каждый момент времени в памяти хранится несколько куч; общий потенциал по определению равен сумме потенциалов всех этих куч. В дальнейшем мы выберем «единицу измерения потенциала» так, чтобы единичного изменения потенциала хватало для оплаты 0(1) операций (формально говоря, мы умножим потенциал на подходящую константу).

В начальном состоянии нет ни одной кучи, и потенциал равен 0. Как и положено (см. разд. 18.3), потенциал всегда неотрицателен.

Максимальная степень

Мы будем предполагать известной некоторую верхнюю границу D(n) для степеней вершин в кучах, которые могут появиться при выполнении наших процедур. (Аргументом функции D является общее число всех вершин в куче, обозначаемое через п.) Если мы используем только операции, предусмотренные для сливаемых куч, то можно положить D(n) = [lgn\ (упр. 21.2-3). В разделе 21.3 мы докажем (для общего случая, когда разрешены также операции Decrease-Key и Delete), что D(n) = O(lgra).

21.2. Операции, предусмотренные для сливаемых куч

Для начала мы будем рассматривать лишь операции Маке-Heap, Insert, Minimum, Extract-Min и Union, предусмотренные для сливаемых куч. В этом случае кучи будут представлять собой набор «неупорядоченных биномиальных деревьев», корни которых связаны в циклический список.

Неупорядоченное биномиальное дерево (unordered binomial tree) получается из упорядоченного, если мы перестаём обращать внимание на порядок среди вершин, имеющих общего родителя. Другими словами, неупорядоченное биномиальное дерево Uo состоит из единственной вершины, а неупорядоченное биномиальное