Fibonacci bunke
Fibonacci heap ( eng. Fibonacci heap ) er en datastruktur, der er et sæt af træer ordnet i overensstemmelse med egenskaben for en ikke-aftagende pyramide. Fibonacci-dynger blev introduceret af Michael Fredman og Robert Tarjan i 1984 .
Strukturen er en implementering af den abstrakte datatype " Priority Queue " og er bemærkelsesværdig ved, at operationer, der ikke kræver sletning, har en amortiseret køretid på (for en binær heap og en binomial heap er den amortiserede køretid ). Ud over standardoperationerne , , , giver Fibonacci-heapen dig mulighed for at udføre operationen med at slå to dynger sammen i tide. INSERTMINDECREASE-KEYUNION
Struktur
- Fibonacci-bunken er en samling af træer .
- Hvert træ i er underlagt heap -egenskaben ( eng. min-heap-egenskab ): nøglen til hver node er ikke mindre end nøglen til dens overordnede node.
- Hver node i indeholder følgende pointere og felter:
- - det felt, hvori nøglen er gemt;
- — pointer til den overordnede node;
- — en pegepind til en af børneknuderne;
- - markør til venstre søsterknude;
- - pointer til højre søsterknude;
- - et felt, der gemmer antallet af børneknuder;
- — en boolsk værdi, der angiver, om knudepunktet har mistet nogen underknudepunkter, siden det blev en underknude til en anden knude.
- Underordnede noder kombineres ved hjælp af pointere til én cyklisk dobbeltforbundet liste over underordnede noder ( eng. child list ) .
- Rødderne af alle træer i er forbundet ved hjælp af pointere og ind i en cyklisk dobbeltforbundet liste af rødder ( eng. root list ).
- For hele Fibonacci-bunken er der også gemt en pointer til noden med minimumsnøglen , som er roden til et af træerne. Denne node kaldes minimumsknuden .
- Det aktuelle antal noder i er gemt i .
![{\displaystyle-tast[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97b36173e5d88ef517878d66a8682fab5bdbabbd)
![{\displaystyle p[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b81272b44de4208e118d4381df4c6828cb52da8)
![{\displaystyle barn[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7983ae8a15176fca40c69829753ebff7acd09cd)
![{\displaystyle venstre[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fa7823fa23979d95eb14ab7667a573c22e01b7a)
![{\displaystyle højre[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11d488d953d9ad638c15d2594ab597b5e653f15e)
![{\displaystyle grad[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fbb4e65cbfec576877633e2ad6ceaaaae241696)
![{\displaystyle mærke[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/542b7e5368647a254202d3b202a71c2df4bf1954)
![{\displaystyle min[H]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c75b5f06b71957bc80e0c4e56425cdf8f30b07)
![{\displaystyle n[H]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92ed2faefa5bfbe5a8314ec6f2b3b1ca9bc406c7)
Operationer
Oprettelse af en ny Fibonacci-bunke
Make_Fib_Heap-proceduren returnerer et fibonacci-heap-objekt , og = NULL. Der er ingen træer .
![{\displaystyle n[H]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6755b0e87ac6248f20059f3300df0f6cb90f896)
Den amortiserede kostpris for en procedure er lig med dens faktiske kostpris .
Indsættelse af en node
Fib_Heap_Insert 1 ← 0 2 ← NULL 3 ← NULL 4 ← 5 ← 6 ← FALSK 7 Vedhæftning af en liste over rødder indeholdende , til en liste over rødder 8 hvis = NULL eller 9 så ← 10 ← + 1
![{\displaystyle-tast[x]<tast[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/678e72a132e9ae0bbee03a96ad87372a80588594)
Den amortiserede kostpris for en procedure er lig med dens faktiske kostpris .
Find minimumsknuden
Fib_Heap_Minimum-proceduren returnerer en .
Den amortiserede kostpris for en procedure er lig med dens faktiske kostpris .
Union af to Fibonacci-dynger
Fib_Heap_Union 1 ← Make_Fib_Heap() 2 ← 3 Tilføjelse af en liste over rødder til en liste over rødder 4 hvis ( = NULL) eller ( ≠ NULL og < ) 5 derefter ← 6 ← 7 Slip objekter og 8 returnerer
![{\displaystyle min[H_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c06be73dfdc2ebd7713d3a946a91127d751c86dd)
![{\displaystyle min[H_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e4c15d462e9bc769e328ba3b93711b75d21de68)
![{\displaystyle-tast[min[H_{2}]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd38f11d72e5ef38a1dba12f4131e25d75e72ccf)
![{\displaystyle-tast[min[H_{1}]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05f66202f4a1f1ef6be319ab0caa46a70aa702da)
![{\displaystyle n[H_{1}]+n[H_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e121253884bf636242ef97daaf19c6dffa47226e)
Den amortiserede kostpris for en procedure er lig med dens faktiske kostpris .
Udpakning af minimumsknuden
Fib_Heap_Extract_Min 1 ← 2 hvis ≠ NULL 3 og derefter for hvert barn af node 4 , skal du tilføje til rodliste 5 ← NULL 6 Fjern fra rodliste 7 hvis = 8 så ← NULL 9 andet ← 10 Konsolider 11 ← 12 retur
![{\displaystyle højre[z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef6c0ca5e045f05b51a8e85a71a2652179a28f23)
![{\displaystyle n[H]-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed2c368ce89423e341bd76679b6a7a18e720e17)
På et af stadierne af operationen med at udtrække minimumsknuden udføres komprimering ( eng. konsolidering ) af listen over rødder . For at gøre dette skal du bruge Consolide helper-proceduren. Denne procedure bruger et hjælpearray . Hvis , så er i øjeblikket en rod med grad .
Konsolider 1 for ← 0 til 2 gør ← NULL 3 for hver node i rodlisten 4 gør ← 5 ← 6 mens ≠ NULL 7 gør ← //Knudepunkt med samme grad som 8 hvis 9 så byt ↔ 10 Fib_Heap_Link 11 ← NULL 12 ← 13 ← 14 ← NULL 15 for ← 0 til 16 gør hvis ≠ NULL 17 derefter Tilføj til rodliste 18 hvis = NULL eller 19 så ← Fib_Heap_Link 1 Fjern fra rodliste 2 Lav underordnet node , øg 3 ← FALSK![{\displaystyle A[0..D[n[H]]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16a8aaf0c3fea41669e247dae3c99739997608c7)
![{\displaystyle A[i]=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1773ac5c49b3da8c9e09a416b77c6fe80c7a307)
![{\displaystyle grad[y]=i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd44fdeab4b5b858a4e9e6d2c45ffcdcf96af6fc)
![{\displaystyle D(n[H])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6561060baee3b079d50a46f93444ab97506a9f5)
![{\displaystyle A[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0d7a8a3371fad84f7032042e8d1e1caf6aa15e)
![{\displaystyle A[d]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/042feac7bdbe07a6252a95c7129cd511404b28ff)
![{\displaystyle-tast[x]>tast[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07c4916c2e2b340131b0a221ca3590ecf2f98357)
![{\displaystyle-tast[A[i]]<tast[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3a421f33d981dab3125f64324a79d34de6ae8f4)
![{\displaystyle mærke[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aecc871ae5dc12bfc3206f13c2a545fcd974bae4)
Den amortiserede pris for at udvinde minimumsknuden er .
Aftagende nøgle
Fib_Heap_Decrease_Key 1 hvis 2 så fejlen "Ny nøgle er større end den nuværende" 3 ← 4 ← 5 hvis ≠ NULL og 6 derefter Cut 7 Cascading_Cut 8 hvis 9 derefter ← Klip 1 Fjern fra listen over underordnede noder , reducer 2 Føj til listen over rødder 3 ← NULL 4 ← FALSK Cascading_Cut 1 ← 2 hvis ≠ NULL 3 så hvis = FALSK 4 derefter ← TRUE 5 andet Klip 6 Cascading_Cut
![{\displaystyle k>tast[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce139201a27c8a99d5bc6e6b21ccff58421d5225)
![{\displaystyle-tast[x]<tast[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b19c276ef004ee01d9243b7dae5ca4d3550d9b6)
![{\displaystyle grad[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a84c755349b58d4dbdf25eee53cabead167a765c)
![{\displaystyle p[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c4860ad95bb383f9e80c71fb26ef7e3c706f92)
Den amortiserede kostpris for nøglereduktion overstiger ikke .
Sletning af en node
Fib_Heap_Delete 1 Fib_Heap_Decrease_Key ∞ 2 Fib_Heap_Extract_Min
Den amortiserede køretid for proceduren er .
Se også
Links
- Strukturimplementering i C
- Vladimir Alekseev, Vladimir Talanov, Foredrag 7: Binomial and Fibonacci Heaps // "Data Structures and Computational Models", 26.09.2006, intuit.ru
Litteratur
- Thomas H. Kormen et al. Algoritmer: konstruktion og analyse. - 2. udg. - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
- Mehlhorn, Kurt, Sanders, Peter. 6.2.2 Fibonacci-dynger // Algoritmer og datastrukturer: Den grundlæggende værktøjskasse. - Springer, 2008. - 300 s. — ISBN 978-3-540-77978-0 .