Die Datenstruktur des Heapsort-Algorithmus

Vorherige Seite Inhaltsverzeichnis Nächste Seite

Heapbaum und Ergebnisliste

Der Heapsort-Algorithmus arbeitet auf einem Heapbaum und einer Ergebnisliste.

Heapbaum und Ergebnisliste können effizient in einem Array gespeichert werden (Implementierung der Datenstruktur).

  1. Anfangs sind alle Schlüssel in einer beliebigen Reihenfolge im Heapbaum und die Ergebnisliste ist leer.
  2. Während der Algorithmus abläuft, werden Schlüssel aus dem Heapbaum in die Ergebnisliste übertragen. Abbildung 1 zeigt eine Momentaufnahme.
  3. Nach Ablauf des Algorithmus ist der Heap leer und die Ergebnisliste enthält die Schlüssel in aufsteigender Sortierung.

Heapbaum und Ergebnisliste

Abbildung 1: Heapbaum (oben) und Ergebnisliste (unten).
Die Schlüssel sind durch Quadrate dargestellt. Die Größe des Quadrats entspricht der Größe des Schlüssels.

Definitionen

Definition: Knoten heapgeordnet

Ein Knoten ist heapgeordnet, wenn der Schlüssel im Knoten größer oder gleich den Schlüsseln in den (direkten) Sohnknoten ist (Abb. 2). Blattknoten sind immer heapgeordnet.

In Abb. 1 sind alle Knoten bis auf den rot umrandeten heapgeordnet.

Heapordnung Knoten
Abbildung 2: Heapordnung an einem Knoten

Definition: Heapbaum

Ein Baum ist ein Heapbaum, wenn er binär, vollständig und heapgeordnet ist.
  1. Binär: Der Grad ist zwei, d.h. ein Knoten hat maximal zwei Söhne.
  2. Vollständig: Alle Ebenen des Baums sind von links nach rechts ohne Lücke gefüllt. Bis auf die letzte Ebene müssen alle Ebenen die maximale Anzahl Knoten enthalten. Unter dieser letzten Ebene können noch leere Ebenen liegen.
  3. Heapgeordnet: Alle Knoten des Baums sind heapgeordnet.

Der Baum in Abbildung 1 ist binär und vollständig. Er ist aber nicht heapgeordnet, da ein Knoten nicht heapgeordnet ist.

Definition: Ergebnisliste

Die Ergebnisliste ist eine Liste, die Schlüssel in aufsteigender Sortierung enthält (Abbildung 1).


Vorherige Seite Inhaltsverzeichnis Nächste Seite