Fibonacci-Heap

Ein Fibonacci-Heap ist eine Datenstruktur zur Implementation einer Priority Queue, die erstmals 1987 von Fredman und Tarjan beschrieben wurde. Im Gegensatz zu einem Binären Heap können in einem Fibonacci-Heap die Operationen Insert (einfügen eines neuen Elementes) und Decrease Key (Ändern des Gewichtes eines Elementes) in amortisiert konstanter Zeit ausgeführt werden. Das Entfernen eines leichtesten Elements ist amortisiert in möglich.

Der Algorithmus von Dijkstra zum Finden aller kürzesten Pfade beziehungswiese der Algorithmus von Prim zum Finden eines minimal spannenden Baumes in einem Graphen lassen sich mit Fibonacci-Heaps mit einer Laufzeit von implementieren.