Фибоначчиева куча
Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное [math]\displaystyle{ O(1) }[/math] (для двоичной кучи и биномиальной кучи амортизационное время работы равно [math]\displaystyle{ O(\log n) }[/math]).
Кроме стандартных операций INSERT, MIN, DECREASE-KEY, фибоначчиева куча позволяет за время [math]\displaystyle{ O(1) }[/math] выполнять операцию UNION слияния двух куч.
Структура
- Фибоначчиева куча [math]\displaystyle{ H }[/math] представляет собой набор деревьев.
- Каждое дерево в [math]\displaystyle{ H }[/math] подчиняется свойству кучи (англ. min-heap property): ключ каждого узла не меньше ключа его родительского узла.
- Каждый узел [math]\displaystyle{ x }[/math] в [math]\displaystyle{ H }[/math] содержит следующие указатели и поля:
- [math]\displaystyle{ key[x] }[/math] — поле, в котором хранится ключ;
- [math]\displaystyle{ p[x] }[/math] — указатель на родительский узел;
- [math]\displaystyle{ child[x] }[/math] — указатель на один из дочерних узлов;
- [math]\displaystyle{ left[x] }[/math] — указатель на левый сестринский узел;
- [math]\displaystyle{ right[x] }[/math] — указатель на правый сестринский узел;
- [math]\displaystyle{ degree[x] }[/math] — поле, в котором хранится количество дочерних узлов;
- [math]\displaystyle{ mark[x] }[/math] — логическое значение, которое указывает, были ли потери узлом [math]\displaystyle{ x }[/math] дочерних узлов, начиная с момента, когда [math]\displaystyle{ x }[/math] стал дочерним узлом какого-то другого узла.
- Дочерние узлы [math]\displaystyle{ x }[/math] объединены при помощи указателей [math]\displaystyle{ left }[/math] и [math]\displaystyle{ right }[/math] в один циклический двусвязный список дочерних узлов (англ. child list) [math]\displaystyle{ x }[/math].
- Корни всех деревьев в [math]\displaystyle{ H }[/math] связаны при помощи указателей [math]\displaystyle{ left }[/math] и [math]\displaystyle{ right }[/math] в циклический двусвязный список корней (англ. root list).
- Для всей Фибоначчиевой кучи также хранится указатель на узел с минимальным ключом [math]\displaystyle{ min[H] }[/math], являющийся корнем одного из деревьев. Этот узел называется минимальным узлом (англ. minimum node) [math]\displaystyle{ H }[/math].
- Текущее количество узлов в [math]\displaystyle{ H }[/math] хранится в [math]\displaystyle{ n[H] }[/math].
Операции
Создание новой фибоначчиевой кучи
Процедура Make_Fib_Heap возвращает объект фибоначчиевой кучи [math]\displaystyle{ H }[/math], [math]\displaystyle{ n[H] = 0 }[/math] и [math]\displaystyle{ min[H] }[/math] = NULL. Деревьев в [math]\displaystyle{ H }[/math] нет.
Амортизированная стоимость процедуры равна её фактической стоимости [math]\displaystyle{ O(1) }[/math].
Вставка узла
Fib_Heap_Insert[math]\displaystyle{ (H,x) }[/math] 1 [math]\displaystyle{ degree[x] }[/math] ← 0 2 [math]\displaystyle{ p[x] }[/math] ← NULL 3 [math]\displaystyle{ child[x] }[/math] ← NULL 4 [math]\displaystyle{ left[x] }[/math] ← [math]\displaystyle{ x }[/math] 5 [math]\displaystyle{ right[x] }[/math] ← [math]\displaystyle{ x }[/math] 6 [math]\displaystyle{ mark[x] }[/math] ← FALSE 7 Присоединение списка корней, содержащего [math]\displaystyle{ x }[/math], к списку корней [math]\displaystyle{ H }[/math] 8 if [math]\displaystyle{ min[H] }[/math] = NULL или [math]\displaystyle{ key[x] \lt key[min[H]] }[/math] 9 then [math]\displaystyle{ min[H] }[/math] ← [math]\displaystyle{ x }[/math] 10 [math]\displaystyle{ n[H] }[/math] ← [math]\displaystyle{ n[H] }[/math] + 1
Амортизированная стоимость процедуры равна её фактической стоимости [math]\displaystyle{ O(1) }[/math].
Поиск минимального узла
Процедура Fib_Heap_Minimum возвращает указатель [math]\displaystyle{ min[H] }[/math].
Амортизированная стоимость процедуры равна её фактической стоимости [math]\displaystyle{ O(1) }[/math].
Объединение двух фибоначчиевых куч
Fib_Heap_Union[math]\displaystyle{ (H_1,H_2) }[/math] 1 [math]\displaystyle{ H }[/math] ← Make_Fib_Heap() 2 [math]\displaystyle{ min[H] }[/math] ← [math]\displaystyle{ min[H_1] }[/math] 3 Добавление списка корней [math]\displaystyle{ H_2 }[/math] к списку корней [math]\displaystyle{ H }[/math] 4 if ([math]\displaystyle{ min[H_1] }[/math] = NULL) или ([math]\displaystyle{ min[H_2] }[/math] ≠ NULL и [math]\displaystyle{ key[min[H_2]] }[/math] < [math]\displaystyle{ key[min[H_1]] }[/math]) 5 then [math]\displaystyle{ min[H] }[/math] ← [math]\displaystyle{ min[H_2] }[/math] 6 [math]\displaystyle{ n[H] }[/math] ← [math]\displaystyle{ n[H_1] + n[H_2] }[/math] 7 Освобождение объектов [math]\displaystyle{ H_1 }[/math] и [math]\displaystyle{ H_2 }[/math] 8 return [math]\displaystyle{ H }[/math]
Амортизированная стоимость процедуры равна её фактической стоимости [math]\displaystyle{ O(1) }[/math].
Извлечение минимального узла
Fib_Heap_Extract_Min[math]\displaystyle{ (H) }[/math] 1 [math]\displaystyle{ z }[/math] ← [math]\displaystyle{ min[H] }[/math] 2 if [math]\displaystyle{ z }[/math] ≠ NULL 3 then for для каждого дочернего по отношению к [math]\displaystyle{ z }[/math] узла [math]\displaystyle{ x }[/math] 4 do Добавить [math]\displaystyle{ x }[/math] в список корней [math]\displaystyle{ H }[/math] 5 [math]\displaystyle{ p[x] }[/math] ← NULL 6 Удалить [math]\displaystyle{ z }[/math] из списка корней [math]\displaystyle{ H }[/math] 7 if [math]\displaystyle{ z }[/math] = [math]\displaystyle{ right[z] }[/math] 8 then [math]\displaystyle{ min[H] }[/math] ← NULL 9 else [math]\displaystyle{ min[H] }[/math] ← [math]\displaystyle{ right[z] }[/math] 10 Consolidate[math]\displaystyle{ (H) }[/math] 11 [math]\displaystyle{ n[H] }[/math] ← [math]\displaystyle{ n[H] - 1 }[/math] 12 return [math]\displaystyle{ z }[/math]
На одном из этапов операции извлечения минимального узла выполняется уплотнение (англ. consolidating) списка корней [math]\displaystyle{ H }[/math]. Для этого используется вспомогательная процедура Consolidate. Эта процедура использует вспомогательный массив [math]\displaystyle{ A[0..D[n[H]]] }[/math]. Если [math]\displaystyle{ A[i] = y }[/math], то [math]\displaystyle{ y }[/math] в настоящий момент является корнем со степенью [math]\displaystyle{ degree[y] = i }[/math].
Consolidate[math]\displaystyle{ (H) }[/math] 1 for [math]\displaystyle{ i }[/math] ← 0 to [math]\displaystyle{ D(n[H]) }[/math] 2 do [math]\displaystyle{ A[i] }[/math] ← NULL 3 for для каждого узла [math]\displaystyle{ w }[/math] в списке корней [math]\displaystyle{ H }[/math] 4 do [math]\displaystyle{ x }[/math] ← [math]\displaystyle{ w }[/math] 5 [math]\displaystyle{ d }[/math] ← [math]\displaystyle{ degree[x] }[/math] 6 while [math]\displaystyle{ A[d] }[/math] ≠ NULL 7 do [math]\displaystyle{ y }[/math] ← [math]\displaystyle{ A[d] }[/math] //Узел с той же степенью, что и у [math]\displaystyle{ x }[/math] 8 if [math]\displaystyle{ key[x] \gt key[y] }[/math] 9 then обменять [math]\displaystyle{ x }[/math] ↔ [math]\displaystyle{ y }[/math] 10 Fib_Heap_Link[math]\displaystyle{ (H,y,x) }[/math] 11 [math]\displaystyle{ A[d] }[/math] ← NULL 12 [math]\displaystyle{ d }[/math] ← [math]\displaystyle{ d + 1 }[/math] 13 [math]\displaystyle{ A[d] }[/math] ← [math]\displaystyle{ x }[/math] 14 [math]\displaystyle{ min[H] }[/math] ← NULL 15 for [math]\displaystyle{ i }[/math] ← 0 to [math]\displaystyle{ D(n[H]) }[/math] 16 do if [math]\displaystyle{ A[i] }[/math] ≠ NULL 17 then Добавить [math]\displaystyle{ A[i] }[/math] в список корней [math]\displaystyle{ H }[/math] 18 if [math]\displaystyle{ min[H] }[/math] = NULL или [math]\displaystyle{ key[A[i]] \lt key[min[H]] }[/math] 19 then [math]\displaystyle{ min[H] }[/math] ← [math]\displaystyle{ A[i] }[/math]
Fib_Heap_Link[math]\displaystyle{ (H,y,x) }[/math] 1 Удалить [math]\displaystyle{ y }[/math] из списка корней [math]\displaystyle{ H }[/math] 2 Сделать [math]\displaystyle{ y }[/math] дочерним узлом [math]\displaystyle{ x }[/math], увеличить [math]\displaystyle{ degree[x] }[/math] 3 [math]\displaystyle{ mark[y] }[/math] ← FALSE
Амортизированная стоимость извлечения минимального узла равна [math]\displaystyle{ O(\log n) }[/math].
Уменьшение ключа
Fib_Heap_Decrease_Key[math]\displaystyle{ (H,x,k) }[/math] 1 if [math]\displaystyle{ k \gt key[x] }[/math] 2 then error «Новый ключ больше текущего» 3 [math]\displaystyle{ key[x] }[/math] ← [math]\displaystyle{ k }[/math] 4 [math]\displaystyle{ y }[/math] ← [math]\displaystyle{ p[x] }[/math] 5 if [math]\displaystyle{ y }[/math] ≠ NULL и [math]\displaystyle{ key[x] \lt key[y] }[/math] 6 then Cut[math]\displaystyle{ (H,x,y) }[/math] 7 Cascading_Cut[math]\displaystyle{ (H,y) }[/math] 8 if [math]\displaystyle{ key[x] \lt key[min[H]] }[/math] 9 then [math]\displaystyle{ min[H] }[/math] ← [math]\displaystyle{ x }[/math]
Cut[math]\displaystyle{ (H,x,y) }[/math] 1 Удаление [math]\displaystyle{ x }[/math] из списка дочерних узлов [math]\displaystyle{ y }[/math], уменьшение [math]\displaystyle{ degree[y] }[/math] 2 Добавление [math]\displaystyle{ x }[/math] в список корней [math]\displaystyle{ H }[/math] 3 [math]\displaystyle{ p[x] }[/math] ← NULL 4 [math]\displaystyle{ mark[x] }[/math] ← FALSE
Cascading_Cut[math]\displaystyle{ (H,y) }[/math] 1 [math]\displaystyle{ z }[/math] ← [math]\displaystyle{ p[y] }[/math] 2 if [math]\displaystyle{ z }[/math] ≠ NULL 3 then if [math]\displaystyle{ mark[y] }[/math] = FALSE 4 then [math]\displaystyle{ mark[y] }[/math] ← TRUE 5 else Cut[math]\displaystyle{ (H,y,z) }[/math] 6 Cascading_Cut[math]\displaystyle{ (H,z) }[/math]
Амортизированная стоимость уменьшения ключа не превышает [math]\displaystyle{ O(1) }[/math].
Удаление узла
Fib_Heap_Delete[math]\displaystyle{ (H,x) }[/math] 1 Fib_Heap_Decrease_Key[math]\displaystyle{ (H,x,- }[/math]∞[math]\displaystyle{ ) }[/math] 2 Fib_Heap_Extract_Min[math]\displaystyle{ (H) }[/math]
Амортизированное время работы процедуры равно [math]\displaystyle{ O(\log n) }[/math].
См. также
Ссылки
- Реализация структуры на 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.