Fibonacci-Heap

Fibonacci-Heaps sind ungeordnete Mengen von Min-Heaps bei denen Knoten markiert werden können. Im Gegensatz zu Binomial-Heaps sind Fibonacci-Heaps „faule“ Datenstukturen. In sie wird direkt eingefügt ohne Aufzuräumen. Dadurch sind bestimmte Operationen ins konstanter Zeit realisierbar. Aufgeräumt (besser: sortiert) wird, sobald das Minimum entfernt werden soll.

Im Folgenden wird aus Gründen der Komplexität und Lesbarkeit auf die Angabe von Pseudocode-Algorithmen verzichtet und jedes Verfahren aus Sicht der prinzipiellen Wirkungsweise beschrieben.

Ein Knoten ist genau dann markiert, wenn er ein Kind verloren hat, d.h. es durch decreaseKey oder delete aus der Position entfernt wurde. Verliert ein markierter Knoten ein weiteres Kind, so wird er zur Wurzelliste hinzugefügt (siehe decreaseKey). Ein Knoten in der Wurzelliste ist nicht (mehr) markiert.

Prinzipiell können auf Fibonacci-Heaps folgende Operationen ausgeführt werden:

• union(fheap1, fheap2): fheap - arbeitet wie union von Binomial-Heaps
• insert(fheap, node)
• decreaseKey(fheap, node, key)
• consolidate(fheap) - das eigentliche „Aufräumen“
• extractMin(fheap): node
• delete(fheap, node)

Das Vereinigen zweier Fibonacci-Heaps erzeugt analog zur Vereinigung zweier Binomial-Heaps.

Das Einfügen erfolgt „faul“ und damit schnell: Es wird ein erzeugt, der den Knoten enthält und dieser zur Wurzelliste hinzugefügt.

Laufzeit:

Auch das Verringern eines Schlüssels wird sehr einfach realisiert. Der entsprechende Schlüssel wird entfernt und der Knoten in die Wurzelliste verschoben. Dabei wird der Vater, wenn er noch nicht markiert war, markiert. War er bereits markiert, wird er abgeschnitten und widerum sein Vater markiert usw.. Dies wird häufig als Cascading Cut bezeichnet. Er bricht ab wenn ein Vater noch nicht markiert war, oder sich der Vater in der Wurzelliste befindet.

Laufzeit: amortisiert

Zunächst wird für jeden Grad ein entsprechender Baum gesucht (sofern vorhanden) und (ein Zeiger auf diesen) vermerkt. Dies wird üblicherweise mit einem Array der Länge ld(n) realisiert. Nun wird durch die Wurzelliste (beginnend beim aktuellen Min-Zeiger, nach rechts gehend) iteriert. Befindet sich der Baum dabei nicht im Array, muss sich somit im Array ein weiterer Baum gleichen Grades befinden, so dass beide verknüpft werden (Vergleich Binomial-Heap). Ist noch kein Baum -ten Grades vermerkt, wird er vermerkt. Ist bereits einer vorhanden, werden beide Bäume erneut verknüpft. Dies wird wiederholt, bis die Wurzelliste durchlaufen wurde. Anschließend existiert von jedem Grad höchstens ein Baum in der Wurzelliste. Nun wird das neue Minimum ermittelt.

Laufzeit:

Zunächst werden (siehe Binomial-Heaps die Kinder des Minimums in die Wurzelliste verschoben. Nun wird der Minimums-Zeiger auf das Element rechts vom Minimum verschoben und das bisherige Minimum gelöscht. Anschließend erfolgt consolidate(fheap), um den Heap aufzuräumen. Dabei wird das neue Minimum ermittelt.

Laufzeit:

Dies geschieht analog zu delete bei Binomial-Heaps.