Фибоначчи куча – Приоритетная очередь на основе бинарной, биномиальной и фибонначиевой куч и ее применение в многоагентных поисковых системах

Содержание

Фибоначчиева куча — Википедия

У этого термина существуют и другие значения, см. Куча.

Фибоначчиева куча (англ. 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 слияния двух куч.

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

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

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

Вставка узла[править | править код]

Fib_Heap_Insert(H,x){\displaystyle (H,x)}
 1 degree[x]{\displaystyle degree[x]} ← 0
 2 p[x]{\displaystyle p[x]} ← NULL
 3 child[x]{\displaystyle child[x]} ← NULL
 4 left[x]{\displaystyle left[x]} ← x{\displaystyle x}
 5 right[x]{\displaystyle right[x]} ← x{\displaystyle x}
 6 mark[x]{\displaystyle mark[x]} ← FALSE
 7 Присоединение списка корней, содержащего x{\displaystyle x}, к списку корней H{\displaystyle H}
 8 if min[H]{\displaystyle min[H]} = NULL или key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
 9    then min[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 возвращает указатель min[H]{\displaystyle min[H]}.

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

Объединение двух фибоначчиевых куч[править | править код]

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

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

Извлечение минимального узла[править | править код]

Fib_Heap_Extract_Min(H){\displaystyle (H)}
 1 z{\displaystyle z} ← min[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} = right[z]{\displaystyle right[z]} 8 then min[H]{\displaystyle min[H]} ← NULL 9 else min[H]{\displaystyle min[H]} ← right[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} в настоящий момент является корнем со степенью degree[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} ← degree[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 key[x]>key[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 min[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 min[H]{\displaystyle min[H]} = NULL или key[A[i]]<key[min[H]]{\displaystyle key[A[i]]<key[min[H]]} 19 then min[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}, увеличить degree[x]{\displaystyle degree[x]}
3 mark[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>key[x]{\displaystyle k>key[x]}
2    then error «Новый ключ больше текущего»
3 key[x]{\displaystyle key[x]} ← k{\displaystyle k}
4 y{\displaystyle y} ← p[x]{\displaystyle p[x]}
5 if y{\displaystyle y} ≠ NULL и key[x]<key[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 key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
9    then min[H]{\displaystyle min[H]} ← x{\displaystyle x}
Cut(H,x,y){\displaystyle (H,x,y)}
1 Удаление x{\displaystyle x} из списка дочерних узлов y{\displaystyle y}, уменьшение degree[y]{\displaystyle degree[y]}
2 Добавление x{\displaystyle x} в список корней H{\displaystyle H}
3 p[x]{\displaystyle p[x]} ← NULL
4 mark[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 mark[y]{\displaystyle mark[y]} = FALSE
4            then mark[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)}.

Фибоначчиева куча — Википедия

У этого термина существуют и другие значения, см. Куча.

Фибоначчиева куча (англ. 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 слияния двух куч.

Структура

Операции

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

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

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

Вставка узла

Fib_Heap_Insert(H,x){\displaystyle (H,x)}
 1 degree[x]{\displaystyle degree[x]} ← 0
 2 p[x]{\displaystyle p[x]} ← NULL
 3 child[x]{\displaystyle child[x]} ← NULL
 4 left[x]{\displaystyle left[x]} ← x{\displaystyle x}
 5 right[x]{\displaystyle right[x]} ← x{\displaystyle x}
 6 mark[x]{\displaystyle mark[x]} ← FALSE
 7 Присоединение списка корней, содержащего x{\displaystyle x}, к списку корней H{\displaystyle H}
 8 
if
min[H]{\displaystyle min[H]} = NULL или key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]} 9 then min[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 возвращает указатель min[H]{\displaystyle min[H]}.

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

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

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

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

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

Fib_Heap_Extract_Min(H){\displaystyle (H)}
 1 z{\displaystyle z} ← min[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} = right[z]{\displaystyle right[z]}
 8            then min[H]{\displaystyle min[H]} ← NULL
 9            else min[H]{\displaystyle min[H]} ← right[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} в настоящий момент является корнем со степенью degree[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} ← degree[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 key[x]>key[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 min[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 min[H]{\displaystyle min[H]} = NULL или key[A[i]]<key[min[H]]{\displaystyle key[A[i]]<key[min[H]]} 19 then min[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}, увеличить degree[x]{\displaystyle degree[x]}
3 mark[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>key[x]{\displaystyle k>key[x]}
2    then error «Новый ключ больше текущего»
3 key[x]{\displaystyle key[x]} ← k{\displaystyle k}
4 y{\displaystyle y} ← p[x]{\displaystyle p[x]}
5 if y{\displaystyle y} ≠ NULL и key[x]<key[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 key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
9    then min[H]{\displaystyle min[H]} ← x{\displaystyle x}
Cut(H,x,y){\displaystyle (H,x,y)}
1 Удаление x{\displaystyle x} из списка дочерних узлов y{\displaystyle y}, уменьшение degree[y]{\displaystyle degree[y]}
2 Добавление x{\displaystyle x} в список корней H{\displaystyle H}
3 p[x]{\displaystyle p[x]} ← NULL
4 mark[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 mark[y]{\displaystyle mark[y]} = FALSE
4            then mark[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)}.

См. также

Ссылки

Литература

Фибоначчиева куча — Википедия

У этого термина существуют и другие значения, см. Куча.

Фибоначчиева куча (англ. 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 слияния двух куч.

Структура

Операции

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

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

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

Вставка узла

Fib_Heap_Insert(H,x){\displaystyle (H,x)}
 1 degree[x]{\displaystyle degree[x]} ← 0
 2 p[x]{\displaystyle p[x]} ← NULL
 3 child[x]{\displaystyle child[x]} ← NULL
 4 left[x]{\displaystyle left[x]} ← x{\displaystyle x}
 5 right[x]{\displaystyle right[x]} ← x{\displaystyle x}
 6 mark[x]{\displaystyle mark[x]} ← FALSE
 7 Присоединение списка корней, содержащего x{\displaystyle x}, к списку корней H{\displaystyle H}
 8 if min[H]{\displaystyle min[H]} = NULL или key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
 9    then min[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 возвращает указатель min[H]{\displaystyle min[H]}.

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

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

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

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

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

Fib_Heap_Extract_Min(H){\displaystyle (H)}
 1 z{\displaystyle z} ← min[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} = right[z]{\displaystyle right[z]}
 8            then min[H]{\displaystyle min[H]} ← NULL
 9            else min[H]{\displaystyle min[H]} ← right[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} в настоящий момент является корнем со степенью degree[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} ← degree[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 key[x]>key[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 min[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 min[H]{\displaystyle min[H]} = NULL или key[A[i]]<key[min[H]]{\displaystyle key[A[i]]<key[min[H]]}
19                   then min[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}, увеличить degree[x]{\displaystyle degree[x]}
3 mark[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>key[x]{\displaystyle k>key[x]}
2    then error «Новый ключ больше текущего»
3 key[x]{\displaystyle key[x]} ← k{\displaystyle k}
4 y{\displaystyle y} ← p[x]{\displaystyle p[x]}
5 if y{\displaystyle y} ≠ NULL и key[x]<key[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 key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
9    then min[H]{\displaystyle min[H]} ← x{\displaystyle x}
Cut(H,x,y){\displaystyle (H,x,y)}
1 Удаление x{\displaystyle x} из списка дочерних узлов y{\displaystyle y}, уменьшение degree[y]{\displaystyle degree[y]}
2 Добавление x{\displaystyle x} в список корней H{\displaystyle H}
3 p[x]{\displaystyle p[x]} ← NULL
4 mark[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 mark[y]{\displaystyle mark[y]} = FALSE
4            then mark[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)}.

См. также

Ссылки

Литература

Фибоначчиева куча — Википедия

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

У этого термина существуют и другие значения, см. Куча.

Фибоначчиева куча (англ. 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 слияния двух куч.

Структура

Видео по теме

Операции

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

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

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

Вставка узла

Fib_Heap_Insert(H,x){\displaystyle (H,x)}
 1 degree[x]{\displaystyle degree[x]} ← 0
 2 p[x]{\displaystyle p[x]} ← NULL
 3 child[x]{\displaystyle child[x]} ← NULL
 4 left[x]{\displaystyle left[x]} ← x{\displaystyle x}
 5 right[x]{\displaystyle right[x]} ← x{\displaystyle x}
 6 mark[x]{\displaystyle mark[x]} ← FALSE
 7 Присоединение списка корней, содержащего x{\displaystyle x}, к списку корней H{\displaystyle H}
 8 if min[H]{\displaystyle min[H]} = NULL или key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
 9    then min[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 возвращает указатель min[H]{\displaystyle min[H]}.

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

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

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

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

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

Fib_Heap_Extract_Min(H){\displaystyle (H)}
 1 z{\displaystyle z} ← min[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}

Фибоначчиева куча - это... Что такое Фибоначчиева куча?

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

Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное (для двоичной кучи и биномиальной кучи амортизационное время работы равно ). Кроме стандартных операций INSERT, MIN, EXTRACT-MIN фибоначчиева куча позволяет за время выполнять операцию UNION слияния двух куч.

Структура

Операции

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

Процедура Make_Fib_Heap возвращает объект фибоначчиевой кучи , и = NULL. Деревьев в нет.

Амортизированная стоимость процедуры равна её фактической стоимости .

Вставка узла

Fib_Heap_Insert
 1  ← 0
 2  ← NULL
 3  ← NULL
 4  ← 
 5  ← 
 6  ← FALSE
 7 Присоединение списка корней, содержащего , к списку корней 
 8 if  = NULL или 
 9    then  ← 
10  ←  + 1

Амортизированная стоимость процедуры равна её фактической стоимости .

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

Процедура Fib_Heap_Minimum возвращает указатель .

Амортизированная стоимость процедуры равна её фактической стоимости .

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

Fib_Heap_Union
1  ← Make_Fib_Heap()
2  ← 
3 Добавление списка корней  к списку корней 
4 if ( = NULL) или ( ≠ NULL и  < )
5    then  ← 
6  ← 
7 Освобождение объектов  и 
8 return 

Амортизированная стоимость процедуры равна её фактической стоимости .

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

Fib_Heap_Extract_Min
 1  ← 
 2 if  ≠ NULL
 3    then for для каждого дочернего по отношению к  узла 
 4             do Добавить  в список корней 
 5                 ← NULL
 6         Удалить  из списка корней 
 7         if  = 
 8            then  ← NULL
 9            else  ← 
10                 Consolidate
11          ← 
12 return 

На одном из этапов операции извлечения минимального узла выполняется уплотнение (англ. consolidating) списка корней . Для этого используется вспомогательная процедура Consolidate. Эта процедура использует вспомогательный массив . Если , то в настоящий момент является корнем со степенью .

Consolidate
 1 for  ← 0 to 
 2     do  ← NULL
 3 for для каждого узла  в списке корней 
 4     do  ← 
 5         ← 
 6        while  ≠ NULL
 7              do  ←  //Узел с той же степенью, что и у 
 8              if 
 9                 then обменять  ↔ 
10              Fib_Heap_Link
11               ← NULL
12               ← 
13         ← 
14  ← NULL
15 for  ← 0 to 
16     do if  ≠ NULL
17           then Добавить  в список корней 
18                if  = NULL или 
19                   then
Fib_Heap_Link
1 Удалить  из списка корней 
2 Сделать  дочерним узлом , увеличить 
3  ← FALSE

Амортизированная стоимость извлечения минимального узла равна .

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

Fib_Heap_Decrease_Key
1 if 
2    then error «Новый ключ больше текущего»
3  ← 
4  ← 
5 if  ≠ NULL и 
6    then Cut
7         Cascading_Cut
8 if 
9    then
Cut
1 Удаление  из списка дочерних узлов , уменьшение 
2 Добавление  в список корней 
3  ← NULL
4  ← FALSE
Cascading_Cut 
1  ← 
2 if  ≠ NULL
3    then if  = FALSE
4            then  ← TRUE
5            else Cut
6                 Cascading_Cut

Амортизированная стоимость уменьшения ключа не превышает .

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

Fib_Heap_Delete
1 Fib_Heap_Decrease_Key∞
2 Fib_Heap_Extract_Min

Амортизированное время работы процедуры равно .

См. также

Ссылки

Литература

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

Фибоначчиева куча Википедия

У этого термина существуют и другие значения, см. Куча.

Фибоначчиева куча (англ. 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 слияния двух куч.

Структура

Операции

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

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

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

Вставка узла

Fib_Heap_Insert(H,x){\displaystyle (H,x)}
 1 degree[x]{\displaystyle degree[x]} ← 0
 2 p[x]{\displaystyle p[x]} ← NULL
 3 child[x]{\displaystyle child[x]} ← NULL
 4 left[x]{\displaystyle left[x]} ← x{\displaystyle x}
 5 right[x]{\displaystyle right[x]} ← x{\displaystyle x}
 6 mark[x]{\displaystyle mark[x]} ← FALSE
 7 Присоединение списка корней, содержащего x{\displaystyle x}, к списку корней H{\displaystyle H}
 8 if min[H]{\displaystyle min[H]} = NULL или key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
 9    then min[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 возвращает указатель min[H]{\displaystyle min[H]}.

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

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

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

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

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

Fib_Heap_Extract_Min(H){\displaystyle (H)}
 1 z{\displaystyle z} ← min[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} = right[z]{\displaystyle right[z]}
 8            then min[H]{\displaystyle min[H]} ← NULL
 9            else min[H]{\displaystyle min[H]} ← right[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} в настоящий момент является корнем со степенью degree[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} ← degree[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 key[x]>key[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 min[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 min[H]{\displaystyle min[H]} = NULL или key[A[i]]<key[min[H]]{\displaystyle key[A[i]]<key[min[H]]}
19                   then min[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}, увеличить degree[x]{\displaystyle degree[x]}
3 mark[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>key[x]{\displaystyle k>key[x]}
2    then error «Новый ключ больше текущего»
3 key[x]{\displaystyle key[x]} ← k{\displaystyle k}
4 y{\displaystyle y} ← p[x]{\displaystyle p[x]}
5 if y{\displaystyle y} ≠ NULL и key[x]<key[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 key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
9    then min[H]{\displaystyle min[H]} ← x{\displaystyle x}
Cut(H,x,y){\displaystyle (H,x,y)}
1 Удаление x{\displaystyle x} из списка дочерних узлов y{\displaystyle y}, уменьшение degree[y]{\displaystyle degree[y]}
2 Добавление x{\displaystyle x} в список корней H{\displaystyle H}
3 p[x]{\displaystyle p[x]} ← NULL
4 mark[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 mark[y]{\displaystyle mark[y]} = FALSE
4            then mark[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)}.

См. также

Ссылки

Литература

Фибоначчиева куча — Википедия. Что такое Фибоначчиева куча

Фибоначчиева куча (англ. 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 слияния двух куч.

Структура

Операции

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

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

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

Вставка узла

Fib_Heap_Insert(H,x){\displaystyle (H,x)}
 1 degree[x]{\displaystyle degree[x]} ← 0
 2 p[x]{\displaystyle p[x]} ← NULL
 3 child[x]{\displaystyle child[x]} ← NULL
 4 left[x]{\displaystyle left[x]} ← x{\displaystyle x}
 5 right[x]{\displaystyle right[x]} ← x{\displaystyle x}
 6 mark[x]{\displaystyle mark[x]} ← FALSE
 7 Присоединение списка корней, содержащего x{\displaystyle x}, к списку корней H{\displaystyle H}
 8 if min[H]{\displaystyle min[H]} = NULL или key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
 9    then min[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 возвращает указатель min[H]{\displaystyle min[H]}.

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

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

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

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

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

Fib_Heap_Extract_Min(H){\displaystyle (H)}
 1 z{\displaystyle z} ← min[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} = right[z]{\displaystyle right[z]}
 8            then min[H]{\displaystyle min[H]} ← NULL
 9            else min[H]{\displaystyle min[H]} ← right[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} в настоящий момент является корнем со степенью degree[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} ← degree[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 key[x]>key[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 min[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 min[H]{\displaystyle min[H]} = NULL или key[A[i]]<key[min[H]]{\displaystyle key[A[i]]<key[min[H]]}
19                   then min[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}, увеличить degree[x]{\displaystyle degree[x]}
3 mark[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>key[x]{\displaystyle k>key[x]}
2    then error «Новый ключ больше текущего»
3 key[x]{\displaystyle key[x]} ← k{\displaystyle k}
4 y{\displaystyle y} ← p[x]{\displaystyle p[x]}
5 if y{\displaystyle y} ≠ NULL и key[x]<key[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 key[x]<key[min[H]]{\displaystyle key[x]<key[min[H]]}
9    then min[H]{\displaystyle min[H]} ← x{\displaystyle x}
Cut(H,x,y){\displaystyle (H,x,y)}
1 Удаление x{\displaystyle x} из списка дочерних узлов y{\displaystyle y}, уменьшение degree[y]{\displaystyle degree[y]}
2 Добавление x{\displaystyle x} в список корней H{\displaystyle H}
3 p[x]{\displaystyle p[x]} ← NULL
4 mark[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 mark[y]{\displaystyle mark[y]} = FALSE
4            then mark[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)}.

См. также

Ссылки

Литература

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *