Daniel Krompass

Quake-Heap vs Fibonacci-Heap: Implementierung, Untersuchung, Bewertung

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 20.06.2013

Kurzbeschreibung

In den vergangenen Jahren wurden zahlreiche Heapalgorithm vorgestellt, welche unterschiedliche Eigenschaften in Sachen Struktur und Performance für ein breites Spektrum von Anwendungen besitzen. Sie werden vor allem für die Realisierung von Priority-Queues, Clustering- oder Graphalgorithmen eingesetzt. Ersteres werden häufig von Schedulern in Servern oder Betriebssystemen verwendet. 2009 stellte [5] die Theorie zu Quake-Heap, einer effizienten Alternative zum vielfach implementierten und untersuchten Fibonacci-Heap, vor. Dieser Algorithmus, so die Behauptung des Autors, soll vor allem durch seine Einfachheit einen pädagogischen mehrwert liefern.

In dieser Arbeit wurde der Quake Heap erstmals implementiert und in zweierlei Hinsicht untersucht. Laufzeitmessungen des Dijkstra Algorithmus auf randomisierten Graphen haben ergeben, dass der Quake-Heap auf der Grundlage mehrerer Messreihen durchschnittlich bessere Werte liefert als der Fibonacci-Heap, was eine praktische Rechtfertigung dieser Datenstruktur liefert. Ebenfalls ließ sich die Datenstruktur
des Quake-Heaps auf Grund der Vermeidung von doppelt verketteten, zyklischen Listen wie sie im Fibonacci-Heap verwendet werden, einfacher implementieren, was für einen höheren pädagogischen Mehrwert spricht.