Aufgaben zu Fibonacci-Heaps
- Im Skript sind verschiedene Einzelheiten ohne Beweis angegeben.
Setzen Sie die fehlenden Beweise ein.
- In F-Bäumen sind die Knotenränge O(log n).
Zeigen Sie, daß die Tiefe Theta(n) erreichen kann,
indem Sie für jedes n
ein Folge von insert, union, decrease_key, extract angeben,
die einen F-Wald erzeugt,
der nur aus einem F-Baum besteht,
der selbst eine lineare Kette von Knoten ist.
- Was passiert, wenn wir nicht nur nach extract,
sondern auch nach jedem union konsolidieren?
Eine Implementierung von Binomial- und Fibonacci-Heaps
finden Sie in miles_span
aus der Stanford Graphbase
von Donald E. Knuth. (Das komplette Buch steht in der Bibliothek.)
