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

20.08.2022

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

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

Структура

Фибоначчиева куча H {displaystyle H} представляет собой набор деревьев.
Каждое дерево в H {displaystyle H} подчиняется свойству кучи (англ. min-heap property): ключ каждого узла не меньше ключа его родительского узла.
Каждый узел x {displaystyle x} в H {displaystyle H} содержит следующие указатели и поля:
- k e y [ x ] {displaystyle key[x]} — поле, в котором хранится ключ;
- p [ x ] {displaystyle p[x]} — указатель на родительский узел;
- c h i l d [ x ] {displaystyle child[x]} — указатель на один из дочерних узлов;
- l e f t [ x ] {displaystyle left[x]} — указатель на левый сестринский узел;
- r i g h t [ x ] {displaystyle right[x]} — указатель на правый сестринский узел;
- d e g r e e [ x ] {displaystyle degree[x]} — поле, в котором хранится количество дочерних узлов;
- m a r k [ x ] {displaystyle mark[x]} — логическое значение, которое указывает, были ли потери узлом x {displaystyle x} дочерних узлов, начиная с момента, когда x {displaystyle x} стал дочерним узлом какого-то другого узла.
Дочерние узлы x {displaystyle x} объединены при помощи указателей l e f t {displaystyle left} и r i g h t {displaystyle right} в один циклический двусвязный список дочерних узлов (англ. child list) x {displaystyle x} .
Корни всех деревьев в H {displaystyle H} связаны при помощи указателей l e f t {displaystyle left} и r i g h t {displaystyle right} в циклический двусвязный список корней (англ. root list).
Для всей Фибоначчиевой кучи также хранится указатель на узел с минимальным ключом m i n [ H ] {displaystyle min[H]} , являющийся корнем одного из деревьев. Этот узел называется минимальным узлом (англ. minimum node) H {displaystyle H} .
Текущее количество узлов в H {displaystyle H} хранится в n [ H ] {displaystyle n[H]} .

Операции

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

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

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

Вставка узла

Fib_Heap_Insert ( H , x ) {displaystyle (H,x)} 1 d e g r e e [ x ] {displaystyle degree[x]} ← 0 2 p [ x ] {displaystyle p[x]} ← NULL 3 c h i l d [ x ] {displaystyle child[x]} ← NULL 4 l e f t [ x ] {displaystyle left[x]} ← x {displaystyle x} 5 r i g h t [ x ] {displaystyle right[x]} ← x {displaystyle x} 6 m a r k [ x ] {displaystyle mark[x]} ← FALSE 7 Присоединение списка корней, содержащего x {displaystyle x} , к списку корней H {displaystyle H} 8 if m i n [ H ] {displaystyle min[H]} = NULL или k e y [ x ] < k e y [ m i n [ H ] ] {displaystyle key[x]<key[min[H]]} 9 then m i n [ H ] {displaystyle min[H]} ← x {displaystyle x} 10 n [ H ] {displaystyle n[H]} ← n [ H ] {displaystyle n[H]} + 1

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

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

Процедура Fib_Heap_Minimum возвращает указатель m i n [ H ] {displaystyle min[H]} .

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

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

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

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

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

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

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

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

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

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

Fib_Heap_Decrease_Key ( H , x , k ) {displaystyle (H,x,k)} 1 if k > k e y [ x ] {displaystyle k>key[x]} 2 then error «Новый ключ больше текущего» 3 k e y [ x ] {displaystyle key[x]} ← k {displaystyle k} 4 y {displaystyle y} ← p [ x ] {displaystyle p[x]} 5 if y {displaystyle y} ≠ NULL и k e y [ x ] < k e y [ y ] {displaystyle key[x]<key[y]} 6 then Cut ( H , x , y ) {displaystyle (H,x,y)} 7 Cascading_Cut ( H , y ) {displaystyle (H,y)} 8 if k e y [ x ] < k e y [ m i n [ H ] ] {displaystyle key[x]<key[min[H]]} 9 then m i n [ H ] {displaystyle min[H]} ← x {displaystyle x} Cut ( H , x , y ) {displaystyle (H,x,y)} 1 Удаление x {displaystyle x} из списка дочерних узлов y {displaystyle y} , уменьшение d e g r e e [ y ] {displaystyle degree[y]} 2 Добавление x {displaystyle x} в список корней H {displaystyle H} 3 p [ x ] {displaystyle p[x]} ← NULL 4 m a r k [ x ] {displaystyle mark[x]} ← FALSE Cascading_Cut ( H , y ) {displaystyle (H,y)} 1 z {displaystyle z} ← p [ y ] {displaystyle p[y]} 2 if z {displaystyle z} ≠ NULL 3 then if m a r k [ y ] {displaystyle mark[y]} = FALSE 4 then m a r k [ y ] {displaystyle mark[y]} ← TRUE 5 else Cut ( H , y , z ) {displaystyle (H,y,z)} 6 Cascading_Cut ( H , z ) {displaystyle (H,z)}

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

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

Fib_Heap_Delete ( H , x ) {displaystyle (H,x)} 1 Fib_Heap_Decrease_Key ( H , x , − {displaystyle (H,x,-} ∞ ) {displaystyle )} 2 Fib_Heap_Extract_Min ( H ) {displaystyle (H)}

Амортизированное время работы процедуры равно O ( log ⁡ n ) {displaystyle O(log n)} .