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

Процедура 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)}$.