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

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