Fibonacci-Heap

In der Informatik ist ein Fibonacci-Heap (englisch heap ‚Halde‘) eine Datenstruktur, ähnlich einem Binomial-Heap, die eine Vorrangwarteschlange realisiert. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge effizient im 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 aufgeprägt. Über der Menge der Schlüssel muss daher eine Totalordnung bestehen, wie sie zum Beispiel die Kleiner-Gleich-Relation (≤) über den ganzen Zahlen darstellt. Fibonacci-Heaps wurden erstmals 1984 von Michael L. Fredman und Robert E. 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,
• 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 Operationen lassen sich mit einer logarithmischen Worst-Case-Laufzeit, also ${\mathcal {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 ${\mathcal {O}}(n)$. Amortisiert sind die Kosten für fast alle anderen Operationen allerdings konstant, das heißt ${\mathcal {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	${\mathcal {O}}(1)$	${\mathcal {O}}(n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$*	${\mathcal {O}}(1)$
getMin	${\mathcal {O}}(n)$	${\mathcal {O}}(1)$	${\mathcal {O}}(1)$	${\mathcal {O}}(1)$	${\mathcal {O}}(1)$
extractMin	${\mathcal {O}}(n)$	${\mathcal {O}}(1)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)$	${\mathcal {O}}(\log n)$*
decreaseKey	${\mathcal {O}}(1)$	${\mathcal {O}}(n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$*	${\mathcal {O}}(1)$*
remove	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$	${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)$**	${\mathcal {O}}(\log n)$*
merge	${\mathcal {O}}(1)$	${\mathcal {O}}(n+m)$	${\mathcal {O}}(m\cdot \log(n+m))$	${\mathcal {O}}(n+m)$	${\mathcal {O}}(1)$

(*) Amortisierte Kosten
(**) Bei bekannter Position, sonst ${\mathcal {O}}(\log n)$*

Datenstruktur

Dieser Fibonacci-Heap hat drei Bäume mit Grad 0, 1 und 3. Drei Knoten sind markiert. Daher ist das Potential des Heaps gleich 9 (3 Bäume + 2 × 3 markierte Knoten).

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. 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 Listen verwendet.

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

Ein Fibonacci-Heap wird normalisiert genannt, wenn alle Bäume unterschiedlichen Wurzelgrad haben, d. h. wenn die Wurzeln der Bäume in der Liste alle unterschiedlich viele Kindknoten haben.

Ein Fibonacci-Heap ist eine Sammlung von 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-Heaps ist die Struktur eines Fibonacci-Heap flexibler. Die Bäume haben keine vorgeschriebene Form und im Extremfall kann der 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 Listen von Bäumen, und die Operation decreaseKey schneidet manchmal einen 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 zu erreichen. Insbesondere wird der Grad der Knoten (hier bedeutet Grad die Anzahl der Kinder) ziemlich niedrig gehalten: Jeder Knoten hat höchstens den Grad ${\mathcal {O}}(\log n)$ und die Größe eines Teilbaums, der in einem Knoten des Grades k verwurzelt ist, beträgt mindestens F_k+2, wobei F_k 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 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 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 Bäume im Fibonacci-Heap und m die Anzahl der markierten 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 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 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 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 in die Liste der Bäume eingefügt und gegebenenfalls der Zeiger auf das minimale Element aktualisiert, wenn der Schlüssel des eingefügten Elementes kleiner als der des bisherigen minimalen Elementes ist. Die Laufzeit ist folglich konstant: ${\mathcal {O}}(1)$

Operation merge

Ä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 gegebenenfalls umgesetzt, wenn der Schlüssel des minimalen Elementes des hinzugefügten Heaps kleiner als der des bisherigen minimalen Elementes ist. Die Laufzeit ist wieder konstant: ${\mathcal {O}}(1)$

Operation decreaseKey

Fibonacci-Heap nach Verringern des Schlüssels von Knoten 9 auf 0. Dieser Knoten sowie seine beiden markierten Vorfahren werden aus dem Baum mit Wurzel 1 herausgeschnitten und als neue Wurzeln platziert.

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 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 in die Liste der Bäume ein.

Um zu vermeiden, dass durch solche Operationen der 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 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 des Grades $k$, d. h. die Wurzel des Baumes hat $k$ Kinder, dann durch die $(k+2)$-te Fibonacci-Zahl $F_{k+2}\geq \varphi ^{k}$ nach unten beschränkt ist, wobei $\varphi$ der goldene Schnitt ${\frac {1+{\sqrt {5}}}{2}}$ ist. Dies ist für die Funktion extractMin von enormer Wichtigkeit.

Operation extractMin sowie cleanup

Der Knoten mit dem minimalen Schlüssel 1 wurde gelöscht und seine untergeordneten Elemente wurden als getrennte Bäume hinzugefügt.

Fibonacci-Heap nach Abschluss der Operation extractMin. Zunächst werden die Knoten 3 und 6 miteinander verbunden. Dann wird das Ergebnis mit dem Baum mit der Wurzel 2 verknüpft.

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 $2\cdot \log 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, 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 $2\cdot \log 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. Die Laufzeit ist also ${\mathcal {O}}(\log n)$.

Operation remove

Das Entfernen eines Elementes aus dem 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 ${\mathcal {O}}(\log n)$, also ergibt sich für die Operation remove eine Laufzeit von ebenfalls ${\mathcal {O}}(\log n)$.

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 eines kürzesten Pfades beziehungsweise der Algorithmus von Prim zum Finden eines minimal spannenden Baumes in einem Graphen mit n Knoten und m Kanten 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.

Literatur

• Michael L. Fredman, Robert E. Tarjan: Fibonacci heaps and their uses in improved network optimization algorithms. In: Journal of the ACM. 34. Jahrgang, Nr. 3, 1987, S. 596–615, doi:10.1145/28869.28874. 

Weblinks

• Gnarley Trees (beinhaltet u. a. Animation als Java-Applet, auch zu anderen Datenstrukturen)