Фибоначчиева куча — Википедия
У этого термина существуют и другие значения, см. Куча.Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1){\displaystyle O(1)} (для двоичной кучи и биномиальной кучи амортизационное время работы равно O(logn){\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(logn){\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(logn){\displaystyle O(\log n)}.
Фибоначчиева куча — Википедия
У этого термина существуют и другие значения, см. Куча.Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1){\displaystyle O(1)} (для двоичной кучи и биномиальной кучи амортизационное время работы равно O(logn){\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(logn){\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(logn){\displaystyle O(\log n)}.
См. также
Ссылки
Литература
Фибоначчиева куча — Википедия
У этого термина существуют и другие значения, см. Куча.Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1){\displaystyle O(1)} (для двоичной кучи и биномиальной кучи амортизационное время работы равно O(logn){\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(logn){\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(logn){\displaystyle O(\log n)}.
См. также
Ссылки
Литература
Фибоначчиева куча — Википедия
Материал из Википедии — свободной энциклопедии
У этого термина существуют и другие значения, см. Куча.Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1){\displaystyle O(1)} (для двоичной кучи и биномиальной кучи амортизационное время работы равно O(logn){\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(logn){\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(logn){\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(logn){\displaystyle O(\log n)}.
См. также
Ссылки
Литература
Фибоначчиева куча — Википедия. Что такое Фибоначчиева куча
Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное O(1){\displaystyle O(1)} (для двоичной кучи и биномиальной кучи амортизационное время работы равно O(logn){\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(logn){\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(logn){\displaystyle O(\log n)}.