WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

См. также

Ссылки

Литература

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии