Daniel Krompass:

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

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.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
20.06.2013