| Datenstruktur
Heapsort wird, wie zu Beginn erwähnt, nur innerhalb einer zugrunde
liegenden Datenstruktur ausgeführt.
Die Element müssen in eine Feldstruktur, z.B. in ein Array
geschrieben werden, es wird also kein binärer Baum erzeugt!
Dies geschieht aus Optimierungsgründen. Die Geschwindigkeit
von Heapsort wäre, würde wirklich auf einem binären Baum
operiert, aufgrund der Zeigerverwaltung erheblich geringer als mittels
einer Feldstruktur.
Die Elemente werden also nur innerhalb ihrer Datenstruktur vertauscht
(daher nennt man Heapsort auch ein internes Sortierverfahren). Und
zwar so lange, bis diese die Heap-Eigenschaft erfüllen:
Für i
von
{2,3,...,n} gilt: A[i/2] >= A[i].
Wenn man nun den sortierten Heap ausgeben will, entfernt man in Wirklichkeit
nicht die Wurzel A[1] , sondern kopiert das
erste (jetzt, nach der Herstellung der Heap-Eigenschaft das größte
Element A[1]) an die letzte Position im Array
A[n].
Das Element an dieser Stelle wird zuvor zwischengespeichert und anschließend
an die erste Stelle im Array kopiert. Anschließend wird die Anzahl
der Elemente n um 1
erniedrigt. Das neue Element an der Stelle A[1]
läßt man innerhalb der Datenstruktur A[1],...,A[n]
absinken. Das Verfahren ist beendet, wenn n=1
ist.
Folglich ist dann das Feld A aufsteigend
sortiert.
|
