Ein Fibonacci-Heap besteht aus mehreren Bäumen in einer
Wurzelliste. Beim Einfügen kommt ein neuer Baum hinzu.
Erst beim Entfernen des Minimums werden Bäume gleichen Grades
konsolidiert.
Heap-Wald
Die oberen Knoten sind die Wurzelliste. Gestrichelte
Verbindungen zeigen ihre Reihenfolge; durchgezogene Linien
sind Eltern-Kind-Beziehungen. Knoten werden als
Schlüssel · ID dargestellt.
Grad: Anzahl direkter Kinder eines Knotens.
Markierung: Ein Nicht-Wurzelknoten wird markiert,
wenn er seit seiner Verknüpfung mit dem Elternknoten bereits
ein Kind verloren hat. Beim nächsten Kindverlust wird auch er
aus seinem Elternbaum herausgeschnitten. Amortisierte Laufzeiten:
Insert O(1),
Decrease-Key O(1),
Extract-Min O(log n).
Die Potenzialfunktion ist
Φ(H) = Anzahl Wurzeln + 2 · Anzahl markierter Knoten.