Fibonacci-Heap

Ein Fibonacci-Heap ist eine Datenstruktur, die sich besonders gut für Priority Queues einsetzen lässt. Sie wurde erstmals 1987 von Michael L. Fredman und Robert E. Tarjan beschrieben.

Operationen

Wie alle für Priority Queues geeignete Datenstrukturen, stellen auch Fibonacci-Heaps die Operationen

• INIT (Initialisieren der Datenstruktur),
• INSERT (Einfügen eines bewerteten Elements) und
• EXTRACT_MIN (Entfernen des kleinsten Elements)

zur Verfügung. Ferner existiert die Operation DECREASE_KEY, mit der der Schlüssel eines Elements verringert werden kann. Herkömmliche Priority Queues können diese Operation durch eine Folge von DELETE und INSERT simulieren.

Laufzeiten

Fibonacci-Heaps können die Funktionen INSERT und DECREASE_KEY in amortisiert konstanter Zeit (O(1)) ausführen und benötigen für die Funktion EXTRACT_MIN amortisiert logarithmisch viel Zeit (O(log n)). Die Initialisierung mit INIT ist ebenfalls in konstanter Zeit möglich.

Im Vergleich zu binären Heaps oder AVL-Bäumen sind Fibonacci-Heaps damit bei den Operationen INSERT und DECREASE_KEY überlegen, denn diese brauchen hier logarithmische Laufzeit. Die Operationen INIT und EXTRACT_MIN besitzen in allen genannten Datenstrukturen gleiche Komplexität.

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

implementieren. Mit AVL-Bäumen wären hier nur Laufzeiten von

möglich.

Name

Der Name Fibonacci-Heap rührt von der Analyse der Datenstruktur, bei der die Fibonacci-Zahlen eine große Rolle spielen.