Фибоначчиева куча (англ. 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