Fibonacci-Heap

In der Informatik ist ein Fibonacci-Heap (englisch heap ‚Halde‘) eine Datenstruktur, ähnlich zu einem Binomial-Heap, die sich als Vorrangwarteschlange einsetzen lässt. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge effizient in den Heap hinein gelegt werden können und stets ein Element mit höchster Priorität entnommen werden kann. Im Unterschied zu Binomial-Heaps benötigen fast alle Operationen amortisiert nur konstante Laufzeit.

Die Priorität der Elemente wird diesen durch Schlüssel aufgeprägt. Über der Menge der Schlüssel muss daher eine Totalordnung bestehen, wie sie zum Beispiel die Kleiner-Relation (<) über den ganzen Zahlen darstellt.

Fibonacci-Heaps wurden erstmals 1984 von Michael L. Fredman und Robert Tarjan beschrieben. Ihr Name rührt von der Analyse der Datenstruktur her, bei der Fibonacci-Zahlen eine große Rolle spielen.

Operationen

Fibonacci-Heaps unterstützen effizient die Operationen:

• insert – zum Einfügen eines Elementes,
• remove oder delete – zum Entfernen eines Elementes,
• Min – zum Finden des Elements mit dem minimalen Schlüssel,
• extractMin – zur Rückgabe und zum Entfernen eines Elementes mit minimalem Schlüssel (=höchster Priorität),
• decreaseKey – zum Verringern des Schlüssels eines Elementes und
• merge oder union – zum Verschmelzen zweier Heaps.

Laufzeiten

Alle Operationen lassen sich mit einer logarithmischen Worst-Case-Laufzeit, also O(log n), 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, also O(n). Amortisiert sind die Kosten für fast alle anderen Operationen allerdings konstant, das heißt O(1).

Folglich sind – bei amortisierter Laufzeitanalyse – Fibonacci-Heaps binären Heaps oder Binomial-Heaps 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-Algorithmen, bei denen jede einzelne Operation effizient ausgeführt werden muss.

Laufzeiten im Vergleich:

Operation	Lineare Liste	Sortierte Liste	(Min-)Heap	Unbalancierter Binärbaum	Fibonacci-Heap
insert	O(1)	O(n)	O(log n)	O(log n)*	O(1)
accessMin	O(1)	O(1)	O(1)	O(1)	O(1)
extractMin	O(n)	O(1)	O(log n)	O(1)	O(log n)*
decreaseKey	O(1)	O(n)	O(log n)	O(log n)*	O(1)*
remove	O(n)	O(n)	O(log n)	O(1)¹	O(log n)*
merge	O(1)	O(n + m)	O(m log(n+m))	O(n + m)	O(1)

(*)Amortisierte Kosten (¹)Bei bekannter Position, sonst O(log n)*

Beschreibung der Datenstruktur

Ein Fibonacci-Heap besteht aus einer Liste von Bäumen mit geordneten Nachfolgern, deren 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-Bedingung bezeichnet.

Ein Fibonacci-Heap wird normalisiert genannt, wenn alle Bäume unterschiedlichen Wurzelrang haben.

Implementierung der Operationen

Beim Einfügen eines Elementes mittels insert wird dieses einfach als eigener Baum in die Liste der Bäume eingefügt und ggf. der Zeiger auf das minimale Element aktualisiert, wenn der Schlüssel des eingefügten Elementes kleiner als der des bisherigen minimalen Elementes ist.

Ähnlich einfach gestaltet sich das Verschmelzen zweier Heaps mittels merge. Hier werden die Listen der zu verschmelzenden Bäume einfach verkettet und der Zeiger auf das minimale Element ggf. umgesetzt, wenn der Schlüssel des minimalen Elementes des hinzugefügten Heaps kleiner als der des bisherigen minimalen Elementes ist.

Auch die 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 Heapeigenschaft (alle Kinder größer als der Vater) nicht mehr erfüllt ist. Um diese wieder herzustellen, löscht man das aktualisierte Element aus der Kindliste seines Vaterknotens und fügt ihn als eigenen Baum in die "Liste der Bäume"/Wurzelliste ein. Um zu vermeiden, dass durch solche Operationen der Heap zu sehr in die Breite wächst (dann würde extractMin sehr lange dauern), stellt man nun die Bedingung, dass von jedem Knoten nur ein Kindknoten weggenommen werden darf, ansonsten muss der Knoten selbst aus der Kindliste seines Vaterknotens gecuttet werden 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 des Grades k (also die Wurzel des Baumes hat k Kinder) dann durch die (k + 2)-te Fibonaccizahl $F_{k+2} \geq \varphi^k$ nach unten beschränkt ist, wobei φ der goldene Schnitt $\frac{1+\sqrt{5}}{2}$ ist. Dies ist für die Funktion extractMin von enormer Wichtigkeit.

Nun zu der zentralen Funktion: extractMin. Der Anfang dieser Funktion gestaltet sich recht einfach: Das minimale Element, auf das ja ein Zeiger zeigt, wird ausgegeben, all seine Kinder werden als einzelne Bäume zur Wurzelliste hinzugefügt und das Element selbst wird aus dem 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 Array A von 0 bis 2log n initialisiert. In diesem soll nach dem cleanup an Stelle d ein Zeiger auf einen Baum stehen, wenn in der Wurzelliste ein Element mit Grad d existiert. Es werden also alle Elemente der Wurzelliste in dieses Array eingeordnet. Kommt es dabei zu einer Überschneidung (zwei Elemente haben den gleichen Grad), 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 2log n Elemente im Array stehen. Schließlich muss die neue Wurzelliste aufgebaut werden. Dazu werden alle Elemente des Arrays A durchgegangen und zu einer Liste verschmolzen.

Das Entfernen eines Elementes aus dem Heap mittels remove erfolgt nun, 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.

Bemerkungen

Die Operationen remove und decreaseKey setzen voraus, dass man die Position der entsprechenden Elemente im 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 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 aller kürzesten Pfade beziehungsweise der Algorithmus von Prim zum Finden eines minimal spannenden Baumes in einem Graphen lassen sich mit Fibonacci-Heaps mit der Laufzeit von $\mathcal{O}(n \cdot\log (n) + m)$ implementieren. Mit einem binären oder binomialen Heap wären hier nur Laufzeiten von $\mathcal{O}((n + m)\cdot \log (n))$ möglich (n: Anzahl Knoten, m: Anzahl Kanten im Graph).

Literatur

• Michael L. Fredman und Robert Endre Tarjan: Fibonacci heaps and their uses in improved network optimization algorithms. In: Journal of the ACM, 34 (1987), ISSN 0004-5411, S. 596–615.

Weblinks

• Simulation eines Fibonacci-Heaps (Java-Applet)