Quelltext der Seite Fibonacci-Heap

In der [[Informatik]] ist ein '''Fibonacci-Heap''' ({{EnS|''heap''}} ‚Halde‘) eine [[Datenstruktur]], ähnlich einem [[Binomial-Heap]], die eine [[Vorrangwarteschlange]] realisiert. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge [[Effizienz (Informatik)|effizient]] im [[Heap (Datenstruktur)|Heap]] gespeichert werden können und stets ein Element mit höchster Priorität entnommen werden kann. Die Priorität der Elemente wird diesen durch [[Schlüssel (Informatik)|Schlüssel]] aufgeprägt. Über der Menge der Schlüssel muss daher eine [[Totalordnung]] bestehen, wie sie zum Beispiel die Kleiner-Gleich-Relation (≤) über den [[ganze Zahl|ganzen Zahlen]] darstellt. Fibonacci-Heaps wurden erstmals [[1984]] von [[Michael L. Fredman]] und [[Robert Tarjan|Robert E. Tarjan]] beschrieben. Ihr Name rührt von der Analyse der Datenstruktur her, bei der [[Fibonacci-Folge|Fibonacci-Zahlen]] eine große Rolle spielen.

== Operationen ==
Fibonacci-Heaps unterstützen effizient die [[Operation (Informatik)|Operationen]]:
* ''insert'' – zum Einfügen eines Elementes,
* ''remove'' oder ''delete'' – zum Entfernen eines Elementes,
* ''getMin'' – zum Finden des Elements mit dem minimalen Schlüssel,
* ''extractMin'' – zur Rückgabe und zum Entfernen eines Elementes mit minimalem Schlüssel, also höchster Priorität,
* ''decreaseKey'' – zum Verringern des Schlüssels eines Elementes und
* ''merge'' oder ''union'' – zum Verschmelzen zweier Heaps.

== Laufzeiten ==
Alle [[Operation (Informatik)|Operationen]] lassen sich mit einer [[Logarithmus|logarithmischen]] [[Asymptotische Laufzeit|Worst-Case-Laufzeit]], also <math>\mathcal{O}(\log n)</math>, implementieren, wobei ''n'' die Zahl der aktuell im Heap befindlichen Elemente ist. Lediglich die Operationen ''remove'', ''extractMin'' und ''decreaseKey'' benötigen im Worst-Case lineare [[Laufzeit (Informatik)|Laufzeit]], also <math>\mathcal{O}(n)</math>. Amortisiert sind die Kosten für fast alle anderen Operationen allerdings konstant, das heißt <math>\mathcal{O}(1)</math>.

Folglich sind – bei [[Amortisierte Laufzeitanalyse|amortisierter Laufzeitanalyse]] – Fibonacci-Heaps [[binärer Heap|binären Heaps]] oder [[Binomial-Heap]]s bei der Ausführung der Operationen ''insert'' und ''merge'' überlegen. Allerdings eignen sie sich wegen der schlechten Worst-Case-Laufzeit von ''remove'', ''extractMin'' und ''decreaseKey'' weniger für [[Online-Algorithmus|Online-Algorithmen]], bei denen jede einzelne Operation effizient ausgeführt werden muss.

[[Laufzeit (Informatik)|Laufzeiten]] im Vergleich:

{| class="wikitable"
|-
! Operation
! Lineare Liste
! Sortierte Liste
! (Min-)Heap
! Unbalancierter Binärbaum
! Fibonacci-Heap
|-
| insert
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(\log n)</math>
| <math>\mathcal{O}(\log n)</math>
| <math>\mathcal{O}(\log n)</math>*
| <math>\mathcal{O}(1)</math>
|-
| getMin
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(1)</math>
|-
| extractMin
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(\log n)</math>
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(\log n)</math>*
|-
| decreaseKey
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(\log n)</math>
| <math>\mathcal{O}(\log n)</math>*
| <math>\mathcal{O}(1)</math>*
|-
| remove
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(\log n)</math>
| <math>\mathcal{O}(1)</math>**
| <math>\mathcal{O}(\log n)</math>*
|-
| merge
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(n + m)</math>
| <math>\mathcal{O}(m \cdot \log(n+m))</math>
| <math>\mathcal{O}(n + m)</math>
| <math>\mathcal{O}(1)</math>
|}

(*) Amortisierte Kosten<br />(**) Bei bekannter Position, sonst <math>\mathcal{O}(\log n)</math>*

== Datenstruktur ==
[[Datei:Fibonacci heap.png|mini|250x250px|Dieser Fibonacci-Heap hat drei [[Baum (Graphentheorie)|Bäume]] mit [[Grad (Graphentheorie)|Grad]] 0, 1 und 3. Drei [[Knoten (Graphentheorie)|Knoten]] sind markiert. Daher ist das Potential des [[Heap (Datenstruktur)|Heaps]] gleich 9 (3 Bäume + 2 × 3 markierte Knoten).]]
Ein Fibonacci-Heap besteht aus einer [[Liste (Datenstruktur)|Liste]] von [[Baum (Graphentheorie)|Bäumen]] mit geordneten Nachfolgern, deren [[Knoten (Graphentheorie)|Knoten]] Schlüssel und möglicherweise eine Markierung enthalten. Die durch den Schlüssel aufgeprägte Priorität jedes Knotens ist mindestens so groß wie die Priorität seiner Kinder. Dies wird als [[Heap (Datenstruktur)#Heap-Bedingung|Heap-Bedingung]] bezeichnet. Bei den hier dargestellten ''Min-Heaps'' ist die größere Priorität durch einen kleineren Schlüssel dargestellt.

Sowohl für die Liste der Bäume als auch für die Listen der Kindknoten in den Knoten der Bäume werden zyklische [[doppelt verkettete Liste]]n verwendet.

Zusätzlich wird ein [[Zeiger (Informatik)|Zeiger]] auf das Element mit der größten Priorität, also dem kleinsten Schlüssel, verwaltet.

Ein Fibonacci-Heap wird ''normalisiert'' genannt, wenn alle [[Baum (Graphentheorie)|Bäume]] unterschiedlichen [[Grad (Graphentheorie)|Wurzelgrad]] haben, d.&nbsp;h. wenn die Wurzeln der Bäume in der Liste alle unterschiedlich viele Kindknoten haben.

Ein Fibonacci-Heap ist eine Sammlung von [[Baum (Graphentheorie)|Bäumen]], die die Minimum-Heap-Eigenschaft erfüllen, d. h. der Schlüssel eines Kindes ist immer größer oder gleich dem Schlüssel des Vaters. Dies bedeutet, dass sich der kleinste Schlüssel immer an der Wurzel eines der Bäume befindet. Im Vergleich zu [[Binomial-Heap]]s ist die Struktur eines Fibonacci-Heap flexibler. Die Bäume haben keine vorgeschriebene Form und im Extremfall kann der [[Heap (Datenstruktur)|Heap]] jedes Element in einem getrennten Baum haben. Diese Flexibilität ermöglicht es, einige Vorgänge verzögert auszuführen, wodurch die Arbeit für spätere Vorgänge verschoben wird. Das Zusammenführen von Heaps erfolgt beispielsweise einfach durch Verketten der zwei [[Liste (Datenstruktur)|Listen]] von Bäumen, und die [[Operation (Informatik)|Operation]] ''decreaseKey'' schneidet manchmal einen [[Knoten (Graphentheorie)|Knoten]] von seinem übergeordneten Knoten ab und bildet einen neuen Baum.

Irgendwann muss jedoch eine Reihenfolge in den Heap eingeführt werden, um die gewünschte [[Laufzeit (Informatik)|Laufzeit]] zu erreichen. Insbesondere wird der [[Grad (Graphentheorie)|Grad]] der [[Knoten (Graphentheorie)|Knoten]] (hier bedeutet Grad die Anzahl der Kinder) ziemlich niedrig gehalten: Jeder Knoten hat höchstens den Grad <math>\mathcal{O}(\log n)</math> und die Größe eines Teilbaums, der in einem Knoten des Grades k verwurzelt ist, beträgt mindestens ''F<sub>k+2</sub>'', wobei ''F<sub>k</sub>'' die ''k''-te [[Fibonacci-Zahl]] ist. Dies wird durch die Regel erreicht, dass wir höchstens ein Kind von jedem Nicht-Wurzelknoten abschneiden können. Wenn ein zweites Kind abgeschnitten wird, muss der Knoten selbst von seinem übergeordneten Knoten abgeschnitten werden und wird zur Wurzel eines neuen Baums. Die Anzahl der Bäume wird in der Operation ''extractMin'' verringert, bei der Bäume miteinander verknüpft werden.

Aufgrund einer aufgelockerten Struktur können einige [[Operation (Informatik)|Operationen]] lange dauern, während andere sehr schnell ausgeführt werden. Für die amortisierte Laufzeitanalyse verwenden wir die [[Potentialmethode]], indem wir so tun, als ob sehr schnelle Vorgänge etwas länger dauern als sie tatsächlich sind. Diese zusätzliche Zeit wird dann später kombiniert und von der tatsächlichen [[Laufzeit (Informatik)|Laufzeit]] langsamer Operationen abgezogen. Die für die spätere Verwendung eingesparte Zeit wird zu jedem Zeitpunkt von einer potenziellen Funktion gemessen. Das Potenzial eines Fibonacci-Heap ist gegeben durch ''Potential = t + 2m''.

Dabei ist t die Anzahl der [[Baum (Graphentheorie)|Bäume]] im Fibonacci-Heap und ''m'' die Anzahl der markierten [[Knoten (Graphentheorie)|Knoten]]. Ein Knoten wird markiert, wenn mindestens einer seiner untergeordneten Knoten abgeschnitten wurde, da dieser Knoten zu einem untergeordneten Knoten eines anderen Knotens gemacht wurde. Alle Wurzeln sind nicht markiert. Die amortisierte [[Laufzeit (Informatik)|Laufzeit]] für eine Operation ergibt sich aus der Summe der tatsächlichen Zeit und ''c''-mal der Potentialdifferenz, wobei ''c'' eine Konstante ist.

Somit hat die Wurzel jedes [[Baum (Graphentheorie)|Baums]] in einem Heap eine Zeiteinheit gespeichert. Diese Zeiteinheit kann später verwendet werden, um diesen Baum zum amortisierten Zeitpunkt 0 mit einem anderen Baum zu verknüpfen. Außerdem sind in jedem markierten [[Knoten (Graphentheorie)|Knoten]] zwei Zeiteinheiten gespeichert. Man kann den Knoten von seinem übergeordneten Knoten abschneiden. In diesem Fall wird der Knoten zu einer Wurzel und die zweite Zeiteinheit bleibt wie in jeder anderen Wurzel darin gespeichert.

== Implementierung ==
=== Operation ''insert'' ===
Beim Einfügen eines Elementes mittels ''insert'' wird dieses einfach als eigener [[Baum (Graphentheorie)|Baum]] in die [[Liste (Datenstruktur)|Liste]] der Bäume eingefügt und gegebenenfalls der [[Zeiger (Informatik)|Zeiger]] auf das minimale Element aktualisiert, wenn der Schlüssel des eingefügten Elementes kleiner als der des bisherigen minimalen Elementes ist. Die [[Laufzeit (Informatik)|Laufzeit]] ist folglich konstant: <math>\mathcal{O}(1)</math>

=== Operation ''merge'' ===
Ähnlich einfach gestaltet sich das Verschmelzen zweier [[Heap (Datenstruktur)|Heaps]] mittels ''merge''. Hier werden die [[Liste (Datenstruktur)|Listen]] der zu verschmelzenden [[Baum (Graphentheorie)|Bäume]] einfach verkettet und der [[Zeiger (Informatik)|Zeiger]] auf das minimale Element gegebenenfalls umgesetzt, wenn der Schlüssel des minimalen Elementes des hinzugefügten Heaps kleiner als der des bisherigen minimalen Elementes ist. Die [[Laufzeit (Informatik)|Laufzeit]] ist wieder konstant: <math>\mathcal{O}(1)</math>

=== Operation ''decreaseKey'' ===
[[Datei:Fibonacci heap-decreasekey.png|mini|250x250px|Fibonacci-Heap nach Verringern des Schlüssels von [[Knoten (Graphentheorie)|Knoten]] 9 auf 0. Dieser Knoten sowie seine beiden markierten Vorfahren werden aus dem [[Baum (Graphentheorie)|Baum]] mit Wurzel 1 herausgeschnitten und als neue Wurzeln platziert.]]
Auch die [[Operation (Informatik)|Operation]] ''decreaseKey'' wird in einem Fibonacci-Heap recht faul durchgeführt: Der Schlüssel des zu aktualisierenden Elementes wird zuerst auf den neuen Wert gesetzt. Nun kann es sein, dass die Heap-Eigenschaft, d. h. alle Kinder sind größer als der Vater, nicht mehr erfüllt ist. Um diese wiederherzustellen, löscht man das aktualisierte Element aus der Kindliste seines Vaterknotens und fügt ihn als eigenen [[Baum (Graphentheorie)|Baum]] in die [[Liste (Datenstruktur)|Liste]] der Bäume ein.

Um zu vermeiden, dass durch solche [[Operation (Informatik)|Operationen]] der [[Heap (Datenstruktur)|Heap]] zu sehr in die Breite wächst, denn dann würde ''extractMin'' sehr lange dauern, stellt man nun die Bedingung, dass von jedem [[Knoten (Graphentheorie)|Knoten]] nur ein Kindknoten weggenommen werden darf, ansonsten muss der Knoten selbst aus der Kindliste seines Vaterknotens entfernt werden (Prozedur ''Cut'') usw. Um dies zu realisieren, tritt nun die oben erwähnte Markierung eines Knotens in Erscheinung: ein Knoten ist genau dann markiert, wenn er kein Knoten der Wurzelliste ist und ein Kind aus seiner Kindliste entfernt wurde. Wird nun ein Kind entfernt, dessen Vater markiert war, ruft man die Prozedur ''Cut'' rekursiv auf den Vater auf. Es zeigt sich nach reiflicher mathematischer Analyse, dass die Anzahl an Knoten in einem [[Baum (Graphentheorie)|Baum]] des [[Grad (Graphentheorie)|Grades]] <math>k</math>, d. h. die Wurzel des Baumes hat <math>k</math> Kinder, dann durch die <math>(k+2)</math>-te [[Fibonacci-Zahl]] <math>F_{k+2} \geq \varphi^k</math> nach unten beschränkt ist, wobei <math>\varphi</math> der [[Goldener Schnitt|goldene Schnitt]] <math>\frac{1+\sqrt{5}}{2}</math> ist. Dies ist für die [[Funktion (Programmierung)|Funktion]] ''extractMin'' von enormer Wichtigkeit.

=== Operation ''extractMin'' sowie ''cleanup'' ===
[[Datei:Fibonacci heap extractmin1.png|mini|170x170px|Der [[Knoten (Graphentheorie)|Knoten]] mit dem minimalen Schlüssel 1 wurde gelöscht und seine untergeordneten Elemente wurden als getrennte [[Baum (Graphentheorie)|Bäume]] hinzugefügt.]]
[[Datei:Fibonacci heap extractmin2.png|mini|140x140px|Fibonacci-Heap nach Abschluss der [[Operation (Informatik)|Operation]] ''extractMin''. Zunächst werden die [[Knoten (Graphentheorie)|Knoten]] 3 und 6 miteinander verbunden. Dann wird das Ergebnis mit dem [[Baum (Graphentheorie)|Baum]] mit der Wurzel 2 verknüpft.]]
Nun zu der zentralen [[Funktion (Programmierung)|Funktion]]: ''extractMin''. Der Anfang dieser Funktion gestaltet sich recht einfach: Das minimale Element, auf das ja ein [[Zeiger (Informatik)|Zeiger]] zeigt, wird ausgegeben, all seine Kinder werden als einzelne [[Baum (Graphentheorie)|Bäume]] zur Wurzelliste hinzugefügt und das Element selbst wird aus dem [[Heap (Datenstruktur)|Heap]] entfernt. Nun muss ein neues Minimum bestimmt werden. Da aber keine der bisherigen Funktionen den Heap in die Tiefe wachsen lässt, würde dies eine lineare Zeit dauern. Daher wird der Heap vorher mit der Prozedur ''cleanup'' „aufgeräumt“. Danach werden alle Elemente der Wurzelliste durchgegangen, um ein neues Minimum zu finden.

Die Prozedur ''cleanup'': Hierfür wird zuerst ein [[Feld (Datentyp)|Array]] <math>A</math> von <math>0</math> bis <math>2 \cdot \log n</math> initialisiert. In diesem soll nach dem ''cleanup'' an Stelle <math>d</math> ein [[Zeiger (Informatik)|Zeiger]] auf einen [[Baum (Graphentheorie)|Baum]] stehen, wenn in der Wurzelliste ein Element mit [[Grad (Graphentheorie)|Grad]] <math>d</math> existiert. Es werden also alle Elemente der Wurzelliste in dieses Array eingeordnet. Kommt es dabei zu einer Überschneidung, wenn zwei Elemente den gleichen Grad haben, so wird das Element mit dem kleineren Schlüssel zum Vater des anderen gemacht, der Grad desselben wird erhöht und es wird in das Array einsortiert. Die obige mathematische Analyse versichert, dass höchstens <math>2 \cdot \log n</math> Elemente im Array stehen. Schließlich muss die neue Wurzelliste aufgebaut werden. Dazu werden alle Elemente des Arrays <math>A</math> durchgegangen und zu einer Liste verschmolzen. Die Laufzeit ist also <math>\mathcal{O}(\log n)</math>.

=== Operation ''remove'' ===
Das Entfernen eines Elementes aus dem [[Heap (Datenstruktur)|Heap]] mittels ''remove'' erfolgt, indem zunächst mit ''decreaseKey'' der Schlüssel des zu entfernenden Elementes auf einen Wert kleiner als dem des bisherigen Minimums gesetzt wird. Dadurch wird dieses Element zum neuen minimalen Element. Anschließend kann es mit ''extractMin'' entfernt werden. Die Laufzeit von ''decreaseKey'' ist konstant, die von ''extractMin'' beträgt <math>\mathcal{O}(\log n)</math>, also ergibt sich für die [[Operation (Informatik)|Operation]] ''remove'' eine [[Laufzeit (Informatik)|Laufzeit]] von ebenfalls  <math>\mathcal{O}(\log n)</math>.

== Bemerkungen ==
Die [[Operation (Informatik)|Operationen]] ''remove'' und ''decreaseKey'' setzen voraus, dass man die Position der entsprechenden Elemente im [[Heap (Datenstruktur)|Heap]] kennt. Im Allgemeinen ist es nämlich nicht möglich, effizient ein Element im Heap zu suchen. Daher muss die Operation ''insert'' einen [[Zeiger (Informatik)|Zeiger]] auf den Behälter für das eingefügte Element zurückliefern, den sich das aufrufende Programm im Bedarfsfall an geeigneter Stelle merkt.

== Anwendungen ==
Der [[Algorithmus von Dijkstra]] zum Finden eines [[Kürzester Pfad|kürzesten Pfades]] beziehungsweise der [[Algorithmus von Prim]] zum Finden eines [[minimal spannender Baum|minimal spannenden Baumes]] in einem [[Graph (Graphentheorie)|Graphen]]  mit ''n'' [[Knoten (Graphentheorie)|Knoten]] und ''m'' [[Kante (Graphentheorie)|Kanten]] lassen sich mit Fibonacci-Heaps mit der [[asymptotische Laufzeit|Laufzeit]] von <math>\mathcal{O}(n \cdot\log (n) + m)</math> implementieren. Mit einem [[binärer Heap|binären]] oder [[Binomial-Heap|binomialen Heap]] wären hier nur Laufzeiten von <math>\mathcal{O}((n + m)\cdot \log (n))</math> möglich.

== Literatur ==
* {{cite journal |first1=Michael L. |last1=Fredman |first2=Robert E. |last2=Tarjan |date=1987 |title=Fibonacci heaps and their uses in improved network optimization algorithms |journal=[[Journal of the ACM]] |volume=34 |issue=3 |pages=596–615 |doi=10.1145/28869.28874 |language=en}}

[[Kategorie:Datenstruktur]]