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

См. также

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

Ссылки

• (англ.)
• Владимир Алексеев, Владимир Таланов, // "Структуры данных и модели вычислений", 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 .