Открыть главное меню

Фибоначчиева куча

Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.

Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное (для двоичной кучи и биномиальной кучи амортизационное время работы равно ). Кроме стандартных операций INSERT, MIN, DECREASE-KEY, фибоначчиева куча позволяет за время выполнять операцию 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 

Амортизированное время работы процедуры равно  .

См. такжеПравить

СсылкиПравить

ЛитератураПравить