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

• Фибоначчиева куча ${\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]}$  ← NULL12              ${\displaystyle d}$  ← ${\displaystyle d+1}$ 13        ${\displaystyle A[d]}$  ← ${\displaystyle x}$ 14 ${\displaystyle min[H]}$  ← NULL15 for ${\displaystyle i}$  ← 0 to ${\displaystyle D(n[H])}$ 16     do if ${\displaystyle A[i]}$  ≠ NULL17           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]}$  ← NULL4 ${\displaystyle mark[x]}$  ← FALSE

Cascading_Cut${\displaystyle (H,y)}$  1 ${\displaystyle z}$  ← ${\displaystyle p[y]}$ 2 if ${\displaystyle z}$  ≠ NULL3    then if ${\displaystyle mark[y]}$  = FALSE4            then ${\displaystyle mark[y]}$  ← TRUE5            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.