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

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

Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное ${\displaystyle O(1)}$ (для двоичной кучи и биномиальной кучи амортизационное время работы равно ${\displaystyle O(\log n)}$). Кроме стандартных операций INSERT, MIN, DECREASE-KEY, фибоначчиева куча позволяет за время ${\displaystyle O(1)}$ выполнять операцию UNION слияния двух куч.

• Фибоначчиева куча ${\displaystyle H}$ представляет собой набор деревьев.
• Каждое дерево в ${\displaystyle H}$ подчиняется свойству кучи (англ. min-heap property): ключ каждого узла не меньше ключа его родительского узла.
• Каждый узел ${\displaystyle x}$ в ${\displaystyle H}$ содержит следующие указатели и поля:
  • ${\displaystyle key[x]}$ — поле, в котором хранится ключ;
  • ${\displaystyle p[x]}$ — указатель на родительский узел;
  • ${\displaystyle child[x]}$ — указатель на один из дочерних узлов;
  • ${\displaystyle left[x]}$ — указатель на левый сестринский узел;
  • ${\displaystyle right[x]}$ — указатель на правый сестринский узел;
  • ${\displaystyle degree[x]}$ — поле, в котором хранится количество дочерних узлов;
  • ${\displaystyle mark[x]}$ — логическое значение, которое указывает, были ли потери узлом ${\displaystyle x}$ дочерних узлов, начиная с момента, когда ${\displaystyle x}$ стал дочерним узлом какого-то другого узла.
• Дочерние узлы ${\displaystyle x}$ объединены при помощи указателей ${\displaystyle left}$ и ${\displaystyle right}$ в один циклический двусвязный список дочерних узлов (англ. child list) ${\displaystyle x}$.
• Корни всех деревьев в ${\displaystyle H}$ связаны при помощи указателей ${\displaystyle left}$ и ${\displaystyle right}$ в циклический двусвязный список корней (англ. root list).
• Для всей Фибоначчиевой кучи также хранится указатель на узел с минимальным ключом ${\displaystyle min[H]}$, являющийся корнем одного из деревьев. Этот узел называется минимальным узлом (англ. minimum node) ${\displaystyle H}$.
• Текущее количество узлов в ${\displaystyle H}$ хранится в ${\displaystyle n[H]}$.

Процедура Make_Fib_Heap возвращает объект фибоначчиевой кучи ${\displaystyle H}$, ${\displaystyle n[H]=0}$ и ${\displaystyle min[H]}$ = NULL. Деревьев в ${\displaystyle H}$ нет.

Амортизированная стоимость процедуры равна её фактической стоимости ${\displaystyle O(1)}$.

Fib_Heap_Insert${\displaystyle (H,x)}$  1 ${\displaystyle degree[x]}$ ← 0  2 ${\displaystyle p[x]}$ ← NULL  3 ${\displaystyle child[x]}$ ← NULL  4 ${\displaystyle left[x]}$ ← ${\displaystyle x}$  5 ${\displaystyle right[x]}$ ← ${\displaystyle x}$  6 ${\displaystyle mark[x]}$ ← FALSE  7 Присоединение списка корней, содержащего ${\displaystyle x}$, к списку корней ${\displaystyle H}$  8 if ${\displaystyle min[H]}$ = NULL или ${\displaystyle key[x]<key[min[H]]}$  9    then ${\displaystyle min[H]}$ ← ${\displaystyle x}$ 10 ${\displaystyle n[H]}$ ← ${\displaystyle n[H]}$ + 1 

Амортизированная стоимость процедуры равна её фактической стоимости ${\displaystyle O(1)}$.

Процедура Fib_Heap_Minimum возвращает указатель ${\displaystyle min[H]}$.

Амортизированная стоимость процедуры равна её фактической стоимости ${\displaystyle O(1)}$.

Fib_Heap_Union${\displaystyle (H_{1},H_{2})}$ 1 ${\displaystyle H}$ ← Make_Fib_Heap() 2 ${\displaystyle min[H]}$ ← ${\displaystyle min[H_{1}]}$ 3 Добавление списка корней ${\displaystyle H_{2}}$ к списку корней ${\displaystyle H}$ 4 if (${\displaystyle min[H_{1}]}$ = NULL) или (${\displaystyle min[H_{2}]}$ ≠ NULL и ${\displaystyle key[min[H_{2}]]}$ < ${\displaystyle key[min[H_{1}]]}$) 5    then ${\displaystyle min[H]}$ ← ${\displaystyle min[H_{2}]}$ 6 ${\displaystyle n[H]}$ ← ${\displaystyle n[H_{1}]+n[H_{2}]}$ 7 Освобождение объектов ${\displaystyle H_{1}}$ и ${\displaystyle H_{2}}$ 8 return ${\displaystyle H}$ 

Амортизированная стоимость процедуры равна её фактической стоимости ${\displaystyle O(1)}$.

Fib_Heap_Extract_Min${\displaystyle (H)}$  1 ${\displaystyle z}$ ← ${\displaystyle min[H]}$  2 if ${\displaystyle z}$ ≠ NULL  3    then for для каждого дочернего по отношению к ${\displaystyle z}$ узла ${\displaystyle x}$  4             do Добавить ${\displaystyle x}$ в список корней ${\displaystyle H}$  5                ${\displaystyle p[x]}$ ← NULL  6         Удалить ${\displaystyle z}$ из списка корней ${\displaystyle H}$  7         if ${\displaystyle z}$ = ${\displaystyle right[z]}$  8            then ${\displaystyle min[H]}$ ← NULL  9            else ${\displaystyle min[H]}$ ← ${\displaystyle right[z]}$ 10                 Consolidate${\displaystyle (H)}$ 11         ${\displaystyle n[H]}$ ← ${\displaystyle n[H]-1}$ 12 return ${\displaystyle z}$ 

На одном из этапов операции извлечения минимального узла выполняется уплотнение (англ. consolidating) списка корней ${\displaystyle H}$. Для этого используется вспомогательная процедура Consolidate. Эта процедура использует вспомогательный массив ${\displaystyle A[0..D[n[H]]]}$. Если ${\displaystyle A[i]=y}$, то ${\displaystyle y}$ в настоящий момент является корнем со степенью ${\displaystyle degree[y]=i}$.

Consolidate${\displaystyle (H)}$  1 for ${\displaystyle i}$ ← 0 to ${\displaystyle D(n[H])}$  2     do ${\displaystyle A[i]}$ ← NULL  3 for для каждого узла ${\displaystyle w}$ в списке корней ${\displaystyle H}$  4     do ${\displaystyle x}$ ← ${\displaystyle w}$  5        ${\displaystyle d}$ ← ${\displaystyle degree[x]}$  6        while ${\displaystyle A[d]}$ ≠ NULL  7              do ${\displaystyle y}$ ← ${\displaystyle A[d]}$ //Узел с той же степенью, что и у ${\displaystyle x}$  8              if ${\displaystyle key[x]>key[y]}$  9                 then обменять ${\displaystyle x}$ ↔ ${\displaystyle y}$ 10              Fib_Heap_Link${\displaystyle (H,y,x)}$ 11              ${\displaystyle A[d]}$ ← NULL 12              ${\displaystyle d}$ ← ${\displaystyle d+1}$ 13        ${\displaystyle A[d]}$ ← ${\displaystyle x}$ 14 ${\displaystyle min[H]}$ ← NULL 15 for ${\displaystyle i}$ ← 0 to ${\displaystyle D(n[H])}$ 16     do if ${\displaystyle A[i]}$ ≠ NULL 17           then Добавить ${\displaystyle A[i]}$ в список корней ${\displaystyle H}$ 18                if ${\displaystyle min[H]}$ = NULL или ${\displaystyle key[A[i]]<key[min[H]]}$ 19                   then ${\displaystyle min[H]}$ ← ${\displaystyle A[i]}$ 

Fib_Heap_Link${\displaystyle (H,y,x)}$ 1 Удалить ${\displaystyle y}$ из списка корней ${\displaystyle H}$ 2 Сделать ${\displaystyle y}$ дочерним узлом ${\displaystyle x}$, увеличить ${\displaystyle degree[x]}$ 3 ${\displaystyle mark[y]}$ ← FALSE 

Амортизированная стоимость извлечения минимального узла равна ${\displaystyle O(\log n)}$.

Fib_Heap_Decrease_Key${\displaystyle (H,x,k)}$ 1 if ${\displaystyle k>key[x]}$ 2    then error «Новый ключ больше текущего» 3 ${\displaystyle key[x]}$ ← ${\displaystyle k}$ 4 ${\displaystyle y}$ ← ${\displaystyle p[x]}$ 5 if ${\displaystyle y}$ ≠ NULL и ${\displaystyle key[x]<key[y]}$ 6    then Cut${\displaystyle (H,x,y)}$ 7         Cascading_Cut${\displaystyle (H,y)}$ 8 if ${\displaystyle key[x]<key[min[H]]}$ 9    then ${\displaystyle min[H]}$ ← ${\displaystyle x}$ 

Cut${\displaystyle (H,x,y)}$ 1 Удаление ${\displaystyle x}$ из списка дочерних узлов ${\displaystyle y}$, уменьшение ${\displaystyle degree[y]}$ 2 Добавление ${\displaystyle x}$ в список корней ${\displaystyle H}$ 3 ${\displaystyle p[x]}$ ← NULL 4 ${\displaystyle mark[x]}$ ← FALSE 

Cascading_Cut${\displaystyle (H,y)}$  1 ${\displaystyle z}$ ← ${\displaystyle p[y]}$ 2 if ${\displaystyle z}$ ≠ NULL 3    then if ${\displaystyle mark[y]}$ = FALSE 4            then ${\displaystyle mark[y]}$ ← TRUE 5            else Cut${\displaystyle (H,y,z)}$ 6                 Cascading_Cut${\displaystyle (H,z)}$ 

Амортизированная стоимость уменьшения ключа не превышает ${\displaystyle O(1)}$.

Fib_Heap_Delete${\displaystyle (H,x)}$ 1 Fib_Heap_Decrease_Key${\displaystyle (H,x,-}$∞${\displaystyle )}$ 2 Fib_Heap_Extract_Min${\displaystyle (H)}$ 

Амортизированное время работы процедуры равно ${\displaystyle O(\log n)}$.

• Очередь с приоритетом (программирование)
• Двоичная куча
• Биномиальная куча

• Реализация структуры на C (англ.)
• Владимир Алексеев, Владимир Таланов, Лекция 7: Биномиальные и фибоначчиевы кучи // "Структуры данных и модели вычислений", 26.09.2006, intuit.ru

• Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 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.