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