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.