Fibonacci Heaps

Definition:
Ein Fibonacci Heap ist eine zyklisch verkettete Liste von Bäumen mit einem Zeiger auf den Baum mit minimalem Element (höchster Priorität). Jeder Knoten enthält außer Schlüssel und Wert noch:
- Referenzen zu Vater und Nachbarn (zyklisch verkettete Liste),
- Rang (= Anzahl der Kinder) und
- Markierung $\in \{0,1\}$.

Operationen:

1. $Merge(H_1,H_2)$: Wurzellisten der Heaps verbinden und Minimum-Zeiger aktualisieren, Kosten $O(1)$

2. $Insert$: Element als Baum in die Wurzelliste einfügen, Kosten $O(1)$

3. $ExtractMin$: Minimum ausgeben und Unterbäume in die Wurzelliste einfügen.
Aufräumen: Bäume so lange verschmelzen, bis alle Bäume verschiedenen Wurzelgrad haben. Beim Verschmelzen wird der Baum mit der größeren Wurzel an den Baum mit der kleineren Wurzel angehängt und der Grad der neuen Wurzel um 1 erhöht. Somit betragen die Kosten $O(maxRang+linkSteps)$, Worst Case $O(n)$, amortisiert $O(\log n)$.

4. $DecreaseKey$: Element löschen und mit neuem Wert in die Wurzelliste einfügen. Vater wird markiert oder bei vorhandener Markierung kaskadierend (rekursiv für alle in Folge markierten Väter) abgeschnitten und samt Unterbäume in die Wurzelliste gehängt. Die Markierung zeigt also an, dass ein Knoten schon einmal ein Kind verloren hat, beim kaskadierenden Löschen hat er das zweite Kind verloren. Somit betragen die Kosten $O(maxHeight)$, Worst Case $O(\log n)$, amortisiert $O(1)$.

Eigenschaften:
- $x$ Wurzel, Rang($x$)=$k$ $\Rightarrow$ Baum enthält min. $Fib_{k+2}$ Knoten
- Die Wurzelränge sind logarithmisch beschränkt