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

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

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

Структура

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

Операции

Создание новой фибоначчиевой кучи

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

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

Вставка узла

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

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

Поиск минимального узла

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

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

Объединение двух фибоначчиевых куч

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

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

Извлечение минимального узла

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

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

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

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

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

Уменьшение ключа

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

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

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

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

Удаление узла

Fib_Heap_Delete$(H,x)$
1 Fib_Heap_Decrease_Key$(H,x,-$∞$)$
2 Fib_Heap_Extract_Min$(H)$

Амортизированное время работы процедуры равно $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.