Felicitas Landes:

Rank-Pairing-Heaps und Hollow-Heaps vs. Fibonacci-Heaps - eine theoretische Betrachtung

Kurzbeschreibung

Fusionierbare Heaps wie die Fibonacci-Heaps sind abstrakte Datenstrukturen zur Implementierung einer Prioritätswarteschlange. Mit den Rank-Pairing Heaps und den Hollow Heaps werden zwei Heap-Varianten vorgestellt und bewertet, die mit dem Ansatz entwickelt wurden, die gleichen amortisierten Laufzeiten wie Fibonacci-Heaps bei einfacherer Struktur zu erhalten.

Rank-Pairing Heaps sind klassische, aus Mengen von Bäumen bestehende binäre Heaps, die sich zu beliebiger Form entwickeln können. Sie benötigen nur eine einzige Strukturveränderung während des Verringerns eines Schlüssels und nutzen kaskadierende Rangveränderungen der einzelnen Knoten als Balancebedingung, um die Laufzeiten zu garantieren. Hollow Heaps bestehen aus einem gerichteten azyklischen Graphen. Verzögertes Löschen und Wiedereinfügen von Knoten sorgt in Kombination mit Knotenrängen dafür, dass bei simpler Struktur die amortisierte Laufzeit der Fibonacci-Heaps erreicht wird.

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