Aufgaben zur Anwendung des Wissens über Heapsort

Sie haben im Lernprogramm den Heapsort-Algorithmus kennen gelernt. Sie können in den folgenden Aufgaben Ihr neues Wissen anwenden und prüfen, ob Sie das Lernziel erreicht haben.

1. In einer Implementierung die Bestandteile des Algorithmus erkennen.

Ein Algorithmus kann auf verschiedene Weise realisiert werden. In diesem Lernprogramm wurde der Algorithmus in sechs Funktionen aufgeteilt, es sind aber auch andere Gliederungen möglich. Z.B. wird oft der Programmcode von Heapify-Locally in die Funktion Heapify integriert.

Lesen Sie die Originalveröffentlichung von Heapsort (Englisch) in der er als ALGOL-Programm realisiert ist. Schreiben Sie Anmerkungen zu den Funktionen und Anweisungen, welche Bedeutung sie für den Algorithmus haben. Vermerken Sie, welche Funktionen aus dem Lernprogramm ein Programmteil realisiert.

Die Lösung: Der Original-Heapsort mit Anmerkungen zu den Bestandteilen (in Englisch).

2. Den Algorithmus programmieren

Programmieren Sie den Heapsort-Algorithmus in Java. Gliedern Sie die Funktionen und die Datenstruktur so, wie Sie sie im Lernprogramm kennen gelernt haben. Berücksichtigen Sie auch die Hinweise zur Implementierung der Datenstruktur.

Programmieren Sie die Klasse HeapsortArray mit der folgenden Schnittstelle:

Methode Beschreibung
HeapsortArray(int len) Instanziiert ein leeres HeapsortArray mit Platz für len Knoten (Node).
addNode(Node n) Fügt den Knoten n zum HeapsortArray hinzu. Die Knoten werden nicht heapgeordnet.
heapsort() Sortiert die Knoten im HeapsortArray mit dem Heapsortalgorithmus.
Node getAt(int k) Gibt eine Referenz auf den Knoten zurück, der am Index k gespeichert ist. Der erste Knoten ist bei Index 0 gespeichert.

Eine Lösung für Aufgabe 2 und 3 (in Englisch).

3. Den Algorithmus weiterentwickeln

Man kann mit einem Heapbaum auch eine Prioritätenwarteschlange realisieren. Programmieren Sie eine Prioritätenwarteschlange, die den Heapbaum und einige der Funktionen des Heapsortalgorithmus nutzt. Sie müssen eine neue Algorithmenfunktion programmieren. Programmieren Sie die Klasse PriorityQueue mit der folgenden Schnittstelle:

Methode Beschreibung
PriorityQueue(int len) Instanziiert eine leere Warteschlange mit Platz für len Knoten (Node).
addNode(Node n) Fügt den Knoten n zur Warteschlange hinzu. Stellt die Heapordnung her.
Node getMaxNode() Gibt eine Referenz auf den Knoten mit dem maximalen (größten) Schlüssel zurück. Entfernt den Knoten aus der Warteschlange.

Eine Lösung für Aufgabe 2 und 3 (in Englisch).


Inhaltsverzeichnis