Implementierung der Datenstruktur

Vorherige Seite Inhaltsverzeichnis

Der Algorithmus arbeitet auf einem Heapbaum und einer Ergebnisliste. Sie können effizient in einem Array gespeichert werden. Dadurch entfällt auch der Aufwand für das Aufbauen des Heapbaums und das Umkopieren der Ergebnisliste.

Speicherung im Array

Heapbaum und Ergebnisliste werden zusammen in einem Array gespeichert. Das Array hat so viele Elemente, wie Schlüssel zu sortieren sind. Es wird also kein zusätzlicher Speicherplatz für Zeiger oder Zwischenergebnisse gebraucht. Der vordere Teil des Arrays wird vom Heapbaum belegt, der hintere Teil von der Ergebnisliste (Abbildung 1).

Array-Aufteilung
Abbildung 1: Heapbaum und Ergebnisliste im Array

Bereitstellen der Eingabedaten

Ein Programm, das Schlüssel sortieren möchte, legt diese im Array ab. Der Algorithmus interpretiert das Array anfangs komplett als Heapbaum (der alle Schlüssel enthält). In der Notation der Abbildung 1 füllt dann der grüne Heapbaum komplett das Array aus. Daher muss der Heapbaum nicht aufgebaut werden, sondern ist "sofort da", und zwar vollständig und komplett gefüllt.

Arbeit des Algorithmus

Die Funktion Heapsort führt den gesamten Algorithmus aus. Innerhalb des Algorithmus verschiebt die Funktion Move-Max Schlüssel aus dem Heapbaum in die Ergebnisliste. Dabei wird ein Element aus dem Heap entfernt, wodurch ein Element des Array an der Grenze zur Ergebnisliste frei wird. Die Ergebnisliste hat dadurch Platz, das neue Element aufzunehmen.

Bereitstellen der Ausgabedaten

Nach Ablauf des Algorithmus nimmt die Ergebnisliste das gesamte Array ein. Es ist also auch hier kein Umkopieren nötig, die Ausgabedaten sind nach Ablauf des Algorithmus "sofort da" und können vom Programm aus dem Array ausgelesen werden.

Zuordnung des Heapbaums zum Array

Die Wurzel des Heaps wird im ersten Element des Arrays gespeichert.

Für einen Knoten, der an Position k des Arrays gespeichert ist, wird sein linker Sohn bei 2*k und sein rechter Sohn bei 2*k+1 gespeichert (Abb. 2). Entsprechend findet man die Position des Vaters eines Knoten k durch (k div 2).

Zuordnung der Söhne zu Positionen
Abbildung 2: Zuordnung der Söhne zu Positionen

In der Abbildung 3 ist im Beispielbaum des Lernprogramms neben den Knoten deren Position im Array angegeben.

Positionen der Knoten im Array
Abbildung 3: Positionen der Knoten im Array


Sie haben nun die Kerninhalte des Lernprogramms durchgearbeitet. Vom Inhaltsverzeichnis aus können Sie Aufgaben erreichen, mit denen Sie Ihr erworbenes Wissen prüfen und anwenden können.


Vorherige Seite Inhaltsverzeichnis