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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1) (для двоичной кучи и биномиальной кучи амортизационное время работы равно O(\log n)). Кроме стандартных операций 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].
Fibbonachi kucha.GIF

Операции[править | править вики-текст]

Создание новой фибоначчиевой кучи[править | править вики-текст]

Процедура 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 zmin[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 xw
 5        ddegree[x]
 6        while A[d] ≠ NULL
 7              do yA[d] //Узел с той же степенью, что и у x
 8              if key[x] > key[y]
 9                 then обменять xy
10              Fib_Heap_Link(H,y,x)
11              A[d] ← NULL
12              dd + 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 yp[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 zp[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).

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]