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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное (для двоичной кучи и биномиальной кучи амортизационное время работы равно ). Кроме стандартных операций INSERT, MIN, EXTRACT-MIN, фибоначчиева куча позволяет за время выполнять операцию UNION слияния двух куч.

Структура[править | править вики-текст]

  • Фибоначчиева куча представляет собой набор деревьев.
  • Каждое дерево в подчиняется свойству неубывающей пирамиды (англ. min-heap property): ключ узла не меньше ключа его родительского узла.
  • Каждый узел в содержит следующие указатели и поля:
    • — поле, в котором хранится ключ;
    • — указатель на родительский узел;
    • — указатель на один из дочерних узлов;
    • — указатель на левый сестринский узел;
    • — указатель на правый сестринский узел;
    • — поле, в котором хранится количество дочерних узлов;
    • — логическое значение, которое указывает, были ли потери узлом дочерних узлов, начиная с момента, когда стал дочерним узлом какого-то другого узла.
  • Дочерние узлы объединены при помощи указателей и в один циклический дважды связанный список дочерних узлов (англ. child list) .
  • Корни всех деревьев в связаны при помощи указателей и в циклический дважды связанный список корней (англ. root list).
  • Обращение к выполняется посредством указателя на корень дерева с минимальным ключом. Этот узел называется минимальным узлом (англ. minimum node) .
  • Текущее количество узлов в хранится в .
Fibbonachi kucha.GIF

Операции[править | править вики-текст]

Создание новой фибоначчиевой кучи[править | править вики-текст]

Процедура 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

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]