Структуры данных и модели вычислений
Двусторонние циклические списки удобны по
Рис. 7.2.
Двусторонние циклические списки удобны по двум причинам. Во-первых, из такого списка можно удалить любой узел за время . Во-вторых, два таких списка можно соединить в один за время .
Помимо указанной информации, каждый узел имеет поле , где хранится его степень (число детей), а также поле . В этом поле хранится булевское значение. Смысл его таков:
истинно, если узел потерял ребенка после того, как он в последний раз сделался чьим-либо потомком. Позже будет ясно, как и когда это поле используется.
Корни деревьев, составляющих фибоначчиеву кучу, также связаны с помощью указателей и в двусторонний циклический список, называемый корневым списком. Таким образом, каждый узел фибоначчиевой кучи представляется записью вида
Доступ к куче производится ссылкой
на узел с минимальным ключом. Кроме того, общее число узлов задается атрибутом .
Потенциал. При анализе учетной стоимости операций используют метод потенциала. Пусть — число деревьев в корневом списке кучи , а — количество помеченных узлов. Потенциал определяется формулой
В каждый момент времени в памяти может храниться несколько куч; общий потенциал по определению равен сумме потенциалов всех этих куч. В дальнейшем мы выберем единицу измерения потенциала так, чтобы единичного изменения потенциала хватало для оплаты операций (формально говоря, мы умножим потенциал на подходящую константу). В начальном состоянии нет ни одной кучи и потенциал равен . Как и положено, потенциал всегда неотрицателен.
Максимальная степень Через обозначим верхнюю границу для степеней узлов в кучах, которые могут появиться при выполнении операций. Аргументом функции является общее число всех узлов в куче, обозначаемое через .
Мы не будем углубляться в анализ трудоемкости операций с фибоначчиевыми кучами, отсылая читателя к соответствующей литературе [7], [19]
скажем только, что и все операции, кроме операции удаления элемента, имеют амортизационную трудоемкость , а операция удаления — .
Фибоначчиевы кучи ввел М.Фредман и Р.Тарьян [17].В их статье описаны также приложения фибоначчиевых куч к задачам о кратчайших путях из одной вершины, о кратчайших путях для всех пар вершин, о паросочетаниях с весами и о минимальном покрывающем дереве.
Впоследствии Д.Дрисколл и Р.Тарьян [16]
разработали структуру данных, называемую , как замену для фибоначчиевых куч. Есть две разновидности такой структуры данных. Одна из них дает те же оценки учетной стоимости, что и фибоначчиевы кучи. Другая — позволяет выполнять операцию за время в худшем случае, а операции и Delete — за время
в худшем случае. Эта структура данных имеет также некоторые преимущества по сравнению с фибоначчиевыми кучами при использовании в параллельных алгоритмах.
