Фибоначчиева куча
Материал из Википедии — свободной энциклопедии
Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1) (для двоичной кучи и биномиальной кучи амортизационное время работы равно O(logn)). Кроме стандартных операций INSERT, MIN, EXTRACT-MIN фибоначчиева куча позволяет за время 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).
- Обращение к H выполняется посредством указателя 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(H1,H2) 1 H ← Make_Fib_Heap() 2 min[H] ← min[H1] 3 Добавление списка корней H2 к списку корней H 4 if (min[H1] = NULL) или (min[H2] ≠ NULL и key[min[H2]] < key[min[H1]]) 5 then min[H] ← min[H2] 6 n[H] ← n[H1] + n[H2] 7 Освобождение объектов H1 и H2 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(lgn).
[править] Уменьшение ключа
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(lgn).
[править] См. также
[править] Ссылки
- Визуализатор(англ.)
- Реализация структуры на C(англ.)
- [1] Описание фибоначчиевых куч на intuit.ru
[править] Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4
