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

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

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

См. также

Ссылки

Литература

  • Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4.
  • Mehlhorn, Kurt, Sanders, Peter. 6.2.2 Fibonacci Heaps // Algorithms and Data Structures: The Basic Toolbox. — Springer, 2008. — 300 с. — ISBN 978-3-540-77978-0.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.