Fibonacci-Heap

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Informatik ist ein Fibonacci-Heap (englisch heap ‚Halde‘) eine Datenstruktur, ähnlich zu 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-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[Bearbeiten]

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 (=höchster Priorität),
  • decreaseKey – zum Verringern des Schlüssels eines Elementes und
  • merge oder union – zum Verschmelzen zweier Heaps.

Laufzeiten[Bearbeiten]

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)
getMin O(n) 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[Bearbeiten]

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 (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.

Implementierung der Operationen[Bearbeiten]

Operation insert[Bearbeiten]

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. Die Laufzeit ist folglich konstant: O(1)

Operation merge[Bearbeiten]

Ä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. Die Laufzeit ist wieder konstant: O(1)

Operation decreaseKey[Bearbeiten]

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 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"/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 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 (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 \varphi der goldene Schnitt \frac{1+\sqrt{5}}{2} ist. Dies ist für die Funktion extractMin von enormer Wichtigkeit.

Operation extractMin[Bearbeiten]

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\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 (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 2\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 O(\log n).

Operation remove[Bearbeiten]

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 O(\log n), also ergibt sich für die Operation remove eine Laufzeit von ebenfalls O(\log n).

Bemerkungen[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Weblinks[Bearbeiten]