Heaps und Heapsort

In diesen Unterrichtsunterlagen wollen wir uns der so genannten Heap-Datenstruktur widmen. Diese Datenstruktur ermöglicht es, eine gegebene Menge von Datenpunkten zu verwalten (zum Beispiel eine Menge von natürlichen Zahlen wie {3, 2, 7, 8}), so dass jederzeit neue Elemente effizient hinzugefügt werden können (durch Einfügen der Zahl 4 bekämen wir beispielsweise die neue Menge {3, 2, 7, 8, 4}) und so dass jederzeit das aktuelle Maximum effizient abgerufen und gelöscht werden kann (nach Löschen des aktuellen Maximums 8 würde also die Menge {3, 2, 7, 4} übrig bleiben).

Als Hauptanwendung des Heaps werden wir sehen, wie das bekannte Sortierverfahren Selectionsort von der bisherigen Laufzeit O(n2) auf O(n log n) ohne zusätzlichen Speicherbedarf beschleunigt werden kann. Das resultierende effizientere Sortierverfahren ist unter dem passenden Namen Heapsort bekannt. Folgende Grundlagen und Begriffe werden für die effektive Bearbeitung dieser Unterlagen als Vorwissen vorausgesetzt:

• Asymptotische Notation für Laufzeitanalyse von Algorithmen wie beispielsweise O(n2) oder O(n log n).
• Detailliertes Verständnis der Funktionsweise und Analyse des Sortierverfahrens Selectionsort.
• Vertrautheit mit binären Bäumen und deren Grundbegriffen wie Knoten, Kanten, Eltern und Kinder.
• Kontrollstrukturen, Funktionsaufrufe und Arrays in der Programmiersprache Rust.1

Wir erarbeiten das Thema mit Hilfe von Aufgaben. Diese sind in drei Kategorien unterteilt und können anhand des Symbols, mit dem sie gekennzeichnet sind, unterschieden werden:

• Durch Bearbeiten dieser Knobelaufgaben wird die Schwierigkeit des zu lösenden Problems erkannt, das Interesse für das Problem wird geweckt und wichtige Erkenntnisse für dessen Lösung werden erworben.
• Durch diese Lern- und Projektaufgaben wird entweder eine Thematik weiter vertieft oder ein Schritt in Richtung Lösung des Problems wird selbständig gegangen.
• Durch Lösen dieser Routineaufgaben wird das erworbene Wissen gefestigt und Verständnislücken können aufgedeckt werden.
• Zudem gibt es für die selbständige Auseinandersetzung mit dem Material die folgenden Hilfestellungen:
• Am Ende jedes Abschnitts werden die wichtigsten Konzepte kurz und prägnant zusammengefasst.