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

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

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

См. также

Ссылки

Литература

  • Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4

Wikimedia Foundation. 2010.

Поможем написать диплом

Смотреть что такое "Фибоначчиева куча" в других словарях:

  • Куча (структура данных) — Эта статья  о структуре данных в программировании. О динамической области распределения памяти см. Динамически распределяемая память. Пример полной бинарной кучи …   Википедия

  • Куча (значения) — В Викисловаре есть статья «куча» Куча  нагромождение большого количества объектов, по форме обычно похожее на конус. В переносном смысле  большое количество чего либо. См. парадокс кучи. Содержание …   Википедия

  • Куча (программирование) — Это статья о структуре данных. Статья об области нераспределённой памяти при динамическом распределении памяти называется Куча (нераспределённая память). пример сортирующего дерева Сортирующее дерево (куча, пирамида) такое двоичное дерево, для… …   Википедия

  • Сливаемая куча — У этого термина существуют и другие значения, см. Куча (значения). Сливаемая куча (англ. Mergeable heap) структура данных, которая поддерживает следующие пять операций: Создание пустой кучи (англ. Make heap); Вставка узла в кучу… …   Википедия

  • Двоичная куча — У этого термина существуют и другие значения, см. Куча (значения). Имеется викиучебник по теме « …   Википедия

  • Биномиальная куча — У этого термина существуют и другие значения, см. Куча (значения). Пример биномиальной кучи, содержащий элементы с ключами от 1 до 13 Биномиальная куча (англ. binomial heap) структура данных, реализующая абстрактный тип данных «Очередь с… …   Википедия

  • Очередь с приоритетом — (англ. priority queue)  абстрактный тип данных в программировании, поддерживающий три операции: InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом GetNext: извлечь из очереди и вернуть элемент с минимальным… …   Википедия

  • Список структур данных — …   Википедия

  • Тарьян, Роберт — Необходимо проверить качество перевода и привести статью в соответствие со стилистическими правилами Википедии. Вы можете помочь улучшить эту статью, исправив …   Википедия

  • Роберт Тарьян — Роберт Андре Тарьян Дата рождения: 30 апреля 1948 Место рождения: Помона, Калифорния Научная сфера: Информатика Место работы: Princeton University Альма матер: Калтех, Стэнфорд Награды и премии Премия Тьюринга Робе …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»