Fibonacci-hög

Fibonacci-hög
Typ	högen
Uppfunnet	1984
Uppfunnet av	Michael L. Fredman och Robert Endre Tarjan
Tidskomplexitet i stor O-notation
Algoritm Genomsnitt Värsta fall Föra in Θ (1) Hitta-min Θ (1)   Ta bort-min O(log n )   Minska-knapp Θ (1)   Sammanfoga Θ (1)

Inom datavetenskap är en Fibonacci-hög en datastruktur för prioriterade köoperationer , bestående av en samling högordnade träd . Den har en bättre amorterad körtid än många andra prioriterade ködatastrukturer inklusive binärhögen och binomialhögen . Michael L. Fredman och Robert E. Tarjan utvecklade Fibonacci-högar 1984 och publicerade dem i en vetenskaplig tidskrift 1987. Fibonacci-högar är uppkallade efter Fibonacci-talen , som används i deras körtidsanalys.

För Fibonacci-högen tar fynd-minimumoperationen konstant ( O (1)) amorterad tid. Nyckeloperationerna infoga och minska fungerar också under konstant avskrivningstid. Att ta bort ett element (används oftast i det speciella fallet att ta bort minimielementet) fungerar i O (log n ) amorterad tid, där n är storleken på högen. Detta betyder att med utgångspunkt från en tom datastruktur, skulle varje sekvens av en infoga och minska tangentoperationer och b raderingsoperationer ta O ( a + b log n ) värsta fallet tid, där n är den maximala högstorleken. I en binär eller binomial hög skulle en sådan operationssekvens ta O (( a + b ) log n ) tid. En Fibonacci-hög är alltså bättre än en binär eller binomial hög när b är mindre än a med en icke-konstant faktor. Det är också möjligt att slå samman två Fibonacci-högar under konstant amorterad tid, förbättra den logaritmiska sammanslagningstiden för en binomialhög och förbättra binära högar som inte kan hantera sammanslagningar effektivt.

Att använda Fibonacci-högar för prioriterade köer förbättrar den asymptotiska körtiden för viktiga algoritmer, såsom Dijkstras algoritm för att beräkna den kortaste vägen mellan två noder i en graf, jämfört med samma algoritm som använder andra långsammare prioriterade ködatastrukturer.

Strukturera

Figur 1. Exempel på en Fibonacci-hög. Den har tre träd i graderna 0, 1 och 3. Tre hörn är markerade (visas i blått). Därför är högens potential 9 (3 träd + 2 × (3 markerade hörn)).

En Fibonacci-hög är en samling träd som uppfyller egenskapen minimum-hög , det vill säga nyckeln för ett barn är alltid större än eller lika med nyckeln för föräldern. Detta innebär att miniminyckeln alltid är vid roten av ett av träden. Jämfört med binomialhögar är strukturen hos en Fibonacci-hög mer flexibel. Träden har ingen föreskriven form och i extrema fall kan högen ha varje element i ett separat träd. Denna flexibilitet gör att vissa operationer kan utföras på ett lat sätt, vilket skjuter upp arbetet för senare operationer. Till exempel, sammanfogning av högar görs helt enkelt genom att sammanfoga de två listorna med träd, och operationsminskningstangenten skär ibland en nod från dess förälder och bildar ett nytt träd.

Men någon gång måste ordning införas i högen för att uppnå önskad gångtid. I synnerhet hålls grader av noder (här betyder grad antalet direkta barn) ganska låga: varje nod har högst grad log n och storleken på ett underträd som är rotat i en nod av grad _{k +2} är minst Fk , där F _k är det k :te Fibonacci-talet . Detta uppnås genom regeln att vi kan klippa högst ett barn av varje icke-rotnod. När ett andra barn skärs måste själva noden skäras från sin förälder och blir roten till ett nytt träd (se Bevis på gradgränser, nedan). Antalet träd minskas i operationen delete minimum , där träd är sammanlänkade.

Som ett resultat av en avslappnad struktur kan vissa operationer ta lång tid medan andra görs mycket snabbt. För av amorterad körtid använder vi den potentiella metoden , genom att vi låtsas att mycket snabba operationer tar lite längre tid än vad de faktiskt gör. Denna extra tid kombineras sedan senare och subtraheras från den faktiska körtiden för långsamma operationer. Mängden tid som sparas för senare användning mäts vid varje givet ögonblick av en potentiell funktion. Potentialen hos en Fibonacci-hög ges av

Potential = t + 2 m

där t är antalet träd i Fibonacci-högen och m är antalet markerade noder. En nod är markerad om åtminstone ett av dess underordnade klipptes eftersom denna nod gjordes till ett underordnat av en annan nod (alla rötter är omarkerade). Den avskrivna tiden för en operation ges av summan av den faktiska tiden och c gånger skillnaden i potential, där c är en konstant (vald för att matcha konstantfaktorerna i O- notationen för den faktiska tiden).

Således har roten av varje träd i en hög en tidsenhet lagrad. Denna tidsenhet kan användas senare för att länka detta träd med ett annat träd vid amorterad tid 0. Dessutom har varje markerad nod två tidsenheter lagrade. En kan användas för att klippa noden från dess förälder. Om detta händer blir noden en rot och den andra tidsenheten förblir lagrad i den som i vilken annan rot som helst.

Genomförande av verksamhet

För att möjliggöra snabb radering och sammanlänkning länkas rötterna till alla träd med hjälp av en cirkulär dubbellänkad lista . Barnen till varje nod är också länkade med hjälp av en sådan lista. För varje nod behåller vi dess antal barn och om noden är markerad. Dessutom bibehåller vi en pekare till roten som innehåller miniminyckeln.

Operation find minimum är nu trivial eftersom vi håller pekaren till noden som innehåller den. Det ändrar inte potentialen för högen, därför är både faktisk och upplupet kostnad konstant.

Som nämnts ovan implementeras sammanslagning helt enkelt genom att sammanfoga listorna med trädrötter för de två högarna. Detta kan göras i konstant tid och potentialen förändras inte, vilket igen leder till konstant amorterad tid.

Operation Insert fungerar genom att skapa en ny heap med ett element och göra merge. Detta tar konstant tid, och potentialen ökar med en, eftersom antalet träd ökar. Upplupet anskaffningsvärde är således fortfarande konstant.

Operation extrahera minimum (samma som radera minimum ) fungerar i tre faser. Först tar vi roten som innehåller minimielementet och tar bort det. Dess barn kommer att bli rötter till nya träd. Om antalet barn var d tar det tid O ( d ) att bearbeta alla nya rötter och potentialen ökar med d −1. Därför är den amortiserade körtiden för denna fas O ( d ) = O ( logn ).

Men för att slutföra extrahera minimioperationen måste vi uppdatera pekaren till roten med minsta nyckel. Tyvärr kan det finnas upp till n rötter vi behöver kontrollera. I den andra fasen minskar vi därför antalet rötter genom att successivt koppla samman rötter av samma grad. När två rötter u och v har samma grad, gör vi en av dem till ett barn till den andra så att den med den mindre nyckeln förblir roten. Dess grad kommer att öka med en. Detta upprepas tills varje rot har en annan grad. För att hitta träd av samma grad effektivt använder vi en matris med längden O (log n ) där vi håller en pekare till en rot av varje grad. När en andra rot hittas av samma grad länkas de två och arrayen uppdateras. Den faktiska körtiden är O (log n + m ) där m är antalet rötter i början av den andra fasen. I slutet kommer vi att ha högst O (log n ) rötter (eftersom var och en har olika grad). Därför är skillnaden i potentialfunktionen från före denna fas till efter den: O (log n ) − m , och den amorterade körtiden är då högst O (log n + m ) + c ( O (log n ) − m ). Med ett tillräckligt stort urval av c förenklas detta till O (log n ).

Figur 2. Fibonacci-hög från figur 1 efter första fasen av extraktminimum. Nod med nyckel 1 (minimum) togs bort och dess underordnade träd lades till som separata träd.

Figur 3. Fibonacci-hög från figur 1 efter att extraktminimum har slutförts. Först är noderna 3 och 6 sammanlänkade. Därefter länkas resultatet med träd som är rotat vid nod 2. Slutligen hittas det nya minimumet.

Figur 4. Fibonacci-hög från figur 1 efter minskande nyckel för nod 9 till 0. Denna nod såväl som dess två markerade förfäder skärs från trädet med rötter vid 1 och placeras som nya rötter.

I den tredje fasen kontrollerar vi var och en av de återstående rötterna och hittar minimum. Detta tar O (log n ) tid och potentialen ändras inte. Den totala amorterade drifttiden för extraktminimum är därför O (log n ).

Operation reducering-tangenten kommer att ta noden, minska nyckeln och om heap-egenskapen blir kränkt (den nya nyckeln är mindre än nyckeln för föräldern), klipps noden från sin förälder. Om föräldern inte är en rot markeras den. Om den redan har markerats klipps den också och dess förälder markeras. Vi fortsätter uppåt tills vi når antingen roten eller en omarkerad nod. Nu ställer vi minimumpekaren till det minskade värdet om det är det nya minimumet. I processen skapar vi ett antal, säg k , av nya träd. Vart och ett av dessa nya träd utom möjligen det första markerades ursprungligen men som en rot kommer det att bli omärkt. En nod kan bli markerad. Därför ändras antalet markerade noder med −( k − 1) + 1 = − k + 2. Kombinerar dessa 2 förändringar ändras potentialen med 2(− k + 2) + k = − k + 4. Den faktiska tiden för att utföra skärningen var O ( k ), därför (återigen med ett tillräckligt stort val av c ) är den amorterade körtiden konstant.

Slutligen kan operation delete implementeras helt enkelt genom att minska nyckeln för det element som ska raderas till minus oändlighet, vilket gör det till ett minimum av hela högen. Sedan kallar vi extrahera minimum för att ta bort det. Den avskrivna körtiden för denna operation är O (log n ).

Bevis på examensgränser

Den amorterade prestandan för en Fibonacci-hög beror på graden (antal barn) av någon trädrot som är O (log n ), där n är storleken på högen. Här visar vi att storleken på (under)trädet som är rotat vid valfri nod x av grad d i högen måste ha storleken minst F _{d +2} , där F _k är det k :te Fibonaccitalet . Gradgränsen följer av detta och det faktum (enkelt bevisat med induktion) att $F_{d+2}\geq \varphi ^{d}$ för alla heltal $d \geq 0$ , där $\varphi =(1+{\sqrt {5}})/2\doteq 1,618$ . (Vi har då ${\displaystyle n\geq F_{d+2}\geq \varphi ^{d}} ,$ och tar loggen till basen $\varphi$ av båda sidor ger $d\leq \log _{\varphi }n$ efter behov.)

Betrakta vilken nod x någonstans som helst i högen ( x behöver inte vara roten till ett av huvudträden). Definiera storlek ( x ) som storleken på trädet med rötter i x (antalet avkomlingar till x , inklusive x själv). Vi bevisar genom induktion på höjden av x (längden av en längsta enkel väg från x till ett avledande blad), att storlek ( x ) ≥ F _{d +2} , där d är graden av x .

Basfall: Om x har höjd 0, då är d = 0 och storlek ( x ) = 1 = F ₂ .

Induktivt fall: Antag att x har positiv höjd och grad d > 0. Låt y ₁ , y ₂ , ..., y _d vara barn till x , indexerade i ordning efter de gånger de senast gjordes till barn till x ( y ₁ är den tidigaste och y _d den senaste), och låt c ₁ , c ₂ , ..., c _d vara deras respektive grader. Vi hävdar att c _i ≥ i -2 för varje i med 2 ≤ i ≤ d : Strax innan y _i gjordes till ett barn av x , var y ₁ ,..., y _{i −1} redan barn till x , och så x hade grad minst i −1 vid den tiden. Eftersom träd kombineras endast när graderna av deras rötter är lika, måste det ha varit så att y _i också hade graden minst i -1 när det blev ett barn till x . Från den tiden till idag y _i bara ha förlorat högst ett barn (vilket garanteras av märkningsprocessen), och därför är dess nuvarande grad _c i minst i −2. Detta bevisar påståendet .

Eftersom höjderna för alla y _i är strikt mindre än för x , kan vi tillämpa den induktiva hypotesen på dem för att få storlek ( y _i ) ≥ F _{c i +2} ≥ F _{( i −2)+2} = F _i . Noderna x och y ₁ bidrar vardera med minst 1 till storleken ( x ), och så har vi

${\textbf {size}}(x)\geq 2+\sum _{i=2}^{d}{\textbf {size}}(y_{i})\geq 2+\sum _{ i=2}^{d}F_{i}=1+\summa _{i=0}^{d}F_{i}.$

En rutininduktion bevisar att $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ för alla $d\geq 0$ , vilket ger önskad nedre gräns för storlek ( x ).

Värsta fall

Även om Fibonacci-högar ser väldigt effektiva ut, har de följande två nackdelar:

1. De är komplicerade när det gäller att implementera dem.
2. De är inte lika effektiva i praktiken jämfört med de teoretiskt mindre effektiva formerna av högar. I sin enklaste version kräver de lagring och manipulering av fyra pekare per nod, medan endast två eller tre pekare per nod behövs i andra strukturer, såsom Binary heap , Binomial heap , Pairing heap , Brodal queue och Rank pairing heap.

Även om den totala körtiden för en sekvens av operationer som börjar med en tom struktur begränsas av gränserna som anges ovan, kan vissa (mycket få) operationer i sekvensen ta mycket lång tid att slutföra (särskilt ta bort och ta bort minimum har linjär körtid i i värsta fall). Av denna anledning kanske Fibonacci-högar och andra amorterade datastrukturer inte är lämpliga för realtidssystem . Det är möjligt att skapa en datastruktur som har samma prestanda i värsta fall som Fibonacci-högen har amorterad prestanda. En sådan struktur, Brodalskön , är, med skaparens ord, "ganska komplicerad" och "[inte] tillämplig i praktiken." Den strikta Fibonacci-högen skapades 2012 och är en enklare (jämfört med Brodals) struktur med samma värsta tänkbara gränser. Trots en enklare struktur visar experiment att den strikta Fibonacci-högen i praktiken presterar långsammare än mer komplicerad Brodal-kö och även långsammare än grundläggande Fibonacci-hög. De löpavslappnade högarna av Driscoll et al. ger bra värsta tänkbara prestanda för alla Fibonacci-högoperationer utom merge.

Sammanfattning av löptider

Här är tidskomplexiteten för olika högdatastrukturer. Funktionsnamn antar en min-hög. För betydelsen av " O ( f )" och " Θ ( f )" se Big O-notation .

Drift	hitta-min	radera-min	Föra in	minska-knappen	smälta samman
Binär	Θ (1)	Θ (log n )	O (log n )	O (log n )	Θ ( n )
Vänsterman	Θ (1)	Θ (log n )	Θ (log n )	O (log n )	Θ (log n )
Binom	Θ (1)	Θ (log n )	Θ (1)	Θ (log n )	O (log n )
Fibonacci	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
Parning	Θ (1)	O (log n )	Θ (1)	o (log n )	Θ (1)
Brodal	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
Rank-parning	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
Strikt Fibonacci	Θ (1)	O (log n )	Θ (1)	Θ (1)	Θ (1)
2–3 högar	O (log n )	O (log n )	O (log n )	Θ (1)	?

Praktiska överväganden

Fibonacci-högar har ett rykte om sig att vara långsamma i praktiken på grund av stor minnesförbrukning per nod och höga konstanta faktorer på alla operationer. Nyligen genomförda experimentella resultat tyder på att Fibonacci-högar är mer effektiva i praktiken än de flesta av dess senare derivat, inklusive quake-högar, violation-högar, strikta Fibonacci-högar, rangparningshögar, men mindre effektiva än antingen parningshögar eller arraybaserade högar.

externa länkar

• Java-appletsimulering av en Fibonacci-hög
• MATLAB implementering av Fibonacci heap
• Avrekursiv och minneseffektiv C-implementering av Fibonacci heap (fri/fri programvara, CeCILL-B-licens )
• Ruby-implementering av Fibonacci-högen (med tester)
• Pseudokod för Fibonacci heap-algoritmen
• Olika Java-implementationer för Fibonacci-högen