- Фибоначчиева куча
-
Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное
(для двоичной кучи и биномиальной кучи амортизационное время работы равно
). Кроме стандартных операций
INSERT
,MIN
,EXTRACT-MIN
фибоначчиева куча позволяет за времявыполнять операцию
UNION
слияния двух куч.Содержание
Структура
- Фибоначчиева куча
представляет собой набор деревьев.
- Каждое дерево в
подчиняется свойству неубывающей пирамиды (англ. min-heap property): ключ узла не меньше ключа его родительского узла.
- Каждый узел
в
содержит следующие указатели и поля:
— поле, в котором хранится ключ;
— указатель на родительский узел;
— указатель на один из дочерних узлов;
— указатель на левый сестринский узел;
— указатель на правый сестринский узел;
— поле, в котором хранится количество дочерних узлов;
— логическое значение, которое указывает, были ли потери узлом
дочерних узлов, начиная с момента, когда
стал дочерним узлом какого-то другого узла.
- Дочерние узлы
объединены при помощи указателей
и
в один циклический дважды связанный список дочерних узлов (англ. child list)
.
- Корни всех деревьев в
связаны при помощи указателей
и
в циклический дважды связанный список корней (англ. root list).
- Обращение к
выполняется посредством указателя
на корень дерева с минимальным ключом. Этот узел называется минимальным узлом (англ. minimum node)
.
- Текущее количество узлов в
хранится в
.
Операции
Создание новой фибоначчиевой кучи
Процедура Make_Fib_Heap возвращает объект фибоначчиевой кучи
,
и
= NULL. Деревьев в
нет.
Амортизированная стоимость процедуры равна её фактической стоимости
.
Вставка узла
Fib_Heap_Insert
1
← 0 2
← NULL 3
← NULL 4
←
5
←
6
← FALSE 7 Присоединение списка корней, содержащего
, к списку корней
8 if
= NULL или
9 then
←
10
←
+ 1
Амортизированная стоимость процедуры равна её фактической стоимости
.
Поиск минимального узла
Процедура Fib_Heap_Minimum возвращает указатель
.
Амортизированная стоимость процедуры равна её фактической стоимости
.
Объединение двух фибоначчиевых куч
Fib_Heap_Union
1
← Make_Fib_Heap() 2
←
3 Добавление списка корней
к списку корней
4 if (
= NULL) или (
≠ NULL и
<
) 5 then
←
6
←
7 Освобождение объектов
и
8 return
Амортизированная стоимость процедуры равна её фактической стоимости
.
Извлечение минимального узла
Fib_Heap_Extract_Min
1
←
2 if
≠ NULL 3 then for для каждого дочернего по отношению к
узла
4 do Добавить
в список корней
5
← NULL 6 Удалить
из списка корней
7 if
=
8 then
← NULL 9 else
←
10 Consolidate
11
←
12 return
На одном из этапов операции извлечения минимального узла выполняется уплотнение (англ. consolidating) списка корней
. Для этого используется вспомогательная процедура Consolidate. Эта процедура использует вспомогательный массив
. Если
, то
в настоящий момент является корнем со степенью
.
Consolidate
1 for
← 0 to
2 do
← NULL 3 for для каждого узла
в списке корней
4 do
←
5
←
6 while
≠ NULL 7 do
←
//Узел с той же степенью, что и у
8 if
9 then обменять
↔
10 Fib_Heap_Link
11
← NULL 12
←
13
←
14
← NULL 15 for
← 0 to
16 do if
≠ NULL 17 then Добавить
в список корней
18 if
= NULL или
19 then
←
Fib_Heap_Link
1 Удалить
из списка корней
2 Сделать
дочерним узлом
, увеличить
3
← FALSE
Амортизированная стоимость извлечения минимального узла равна
.
Уменьшение ключа
Fib_Heap_Decrease_Key
1 if
2 then error «Новый ключ больше текущего» 3
←
4
←
5 if
≠ NULL и
6 then Cut
7 Cascading_Cut
8 if
9 then
←
Cut
1 Удаление
из списка дочерних узлов
, уменьшение
2 Добавление
в список корней
3
← NULL 4
← FALSE
Cascading_Cut
1
←
2 if
≠ NULL 3 then if
= FALSE 4 then
← TRUE 5 else Cut
6 Cascading_Cut
Амортизированная стоимость уменьшения ключа не превышает
.
Удаление узла
Fib_Heap_Delete
1 Fib_Heap_Decrease_Key
∞
2 Fib_Heap_Extract_Min
Амортизированное время работы процедуры равно
.
См. также
Ссылки
- Визуализатор (англ.)
- Реализация структуры на C (англ.)
- [1] Описание фибоначчиевых куч на intuit.ru
Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4
Категория:- Кучи (структуры данных)
- Фибоначчиева куча
Wikimedia Foundation. 2010.