Sortierverfahren

Heapsort

Das Sortierverfahren Heapsort [Wil 64] hat eine Zeitkomplexität von Θ(n log(n)). Eine untere Schranke für die Zeitkomplexität von Sortierverfahren ist Ω(n log(n)). Heapsort ist daher optimal, d.h. es gibt kein asymptotisch schnelleres Sortierverfahren.

Heapsort verwendet eine besondere Datenstruktur, die als Heap bezeichnet wird.¹) Diese Datenstruktur wird im Folgenden erklärt; sie basiert auf der Definition eines (fast) vollständigen binären Baums. Ein binärer Baum ist (fast) vollständig, wenn alle Schichten außer möglicherweise der letzten vollständig besetzt sind.

Näheres zur Heap-Datenstruktur siehe auch unter Prioritätenliste.

Definition: Sei T = (V, E) ein (fast) vollständiger binärer Baum mit einer Knotenmarkierung a : V → M, die jedem Knoten u eine Markierung a(u) aus einer geordneten Menge (M, ≤ ) zuordnet.

Ein Knoten u ∈ V hat die Heap-Eigenschaft, wenn er keinen direkten Nachfolgerknoten mit einer größeren Markierung hat, oder anders ausgedrückt, wenn gilt:

∀ v ∈ V : (u, v) ∈ E ⇒ a(u) ≥ a(v) .

T heißt Heap, wenn alle Knoten die Heap-Eigenschaft haben, d.h. wenn gilt:

∀ (u, v) ∈ E : a(u) ≥ a(v) .

Wir nennen T einen Semi-Heap, wenn alle Knoten außer möglicherweise der Wurzel r des Baumes die Heap-Eigenschaft haben, d.h. wenn gilt:

∀ (u, v) ∈ E, u ≠ r : a(u) ≥ a(v) .

Beispiel: In Bild 1 ist ein Heap mit 10 Knoten dargestellt.

Bild 1: Heap mit n = 10 Knoten

Alle Blätter haben automatisch die Heap-Eigenschaft, da sie keine Nachfolgerknoten haben, somit insbesondere keine mit einer größeren Markierung.

Die Datenstruktur des Heapsort-Verfahrens ist ein binärer Baum, dessen Knoten die zu sortierenden Daten enthalten. In der Implementation wird dieser Baum später in einem Array gespeichert. Es ist somit nicht nötig, den Baum als Zeiger-Struktur zu realisieren.

Heapsort-Algorithmus

Die folgende Beschreibung des Heapsort-Algorithmus nimmt Bezug auf Bild 2 (a) - (e).

Entnehmen des maximalen Wertes Löschen des letzten Blattes und Übertragen der Markierung auf die Wurzel Vertauschen der Markierung mit maximaler Markierung der direkten Nachfolger

Vertauschen der Markierung mit maximaler Markierung der direkten Nachfolger Heap wiederhergestellt

Bild 2: Entnehmen des maximalen Elementes und Neuordnen des Heaps

Wenn die zu sortierenden Daten als Heap arrangiert sind, lässt sich das größte Datenelement unmittelbar an der Wurzel des Baumes entnehmen und ausgeben (a). Um das nächstgrößte Element zu entnehmen, müssen die verbleibenden Elemente zunächst als Heap neu angeordnet werden.

Dies geschieht in folgender Weise: Sei b ein Blatt maximaler Tiefe. Die Markierung von b wird an die Stelle der Wurzel geschrieben; anschließend wird b gelöscht (b). Das Ergebnis ist ein Semi-Heap, denn die Wurzel hat nun möglicherweise nicht mehr die Heap-Eigenschaft.

Aus einem Semi-Heap einen Heap zu machen ist einfach: Wenn die Wurzel bereits die Heap-Eigenschaft hat, ist gar nichts zu tun. Wenn nicht, wird ihre Markierung mit der Markierung eines ihrer direkten Nachfolger vertauscht, und zwar mit der maximalen (c). Damit hat nun die Wurzel die Heap-Eigenschaft, aber dafür möglicherweise der entsprechende Nachfolger v nicht mehr. Es wird nun mit v fortgefahren, d.h. der Semi-Heap mit Wurzel v wird zum Heap gemacht (d). Das Verfahren endet spätestens an einem Blatt, da Blätter stets die Heap-Eigenschaft haben (e).

Nachdem nun die verbleibenden Elemente wieder als Heap angeordnet sind, kann das nächstgrößte Element entnommen werden usw. Die Datenelemente werden also in absteigend sortierter Reihenfolge ausgegeben.

Das Umarrangieren eines Semi-Heaps zu einem Heap lässt sich konzeptuell mit folgender Prozedur downheap bewirken:

Prozedur downheap(v)

Eingabe:

Semi-Heap mit Wurzel v

Ausgabe:

Heap (durch Umordnung der Knotenmarken)

Methode:

solange v nicht die Heap-Eigenschaft hat wiederhole

wähle Nachfolgerknoten w mit maximaler Markierung a(w)

vertausche a(v) und a(w)

setze v = w

Die Prozedur downheap wird auch benutzt, um einen (fast) vollständigen binären Baum mit Knotenmarkierung a zu einem Heap zu machen. In folgender Prozedur buildheap werden bottom-up alle Teilbäume mittels downheap zu Heaps gemacht. Statt bei den Blättern zu beginnen, die ja ohnehin bereits die Heap-Eigenschaft haben, genügt es, bei den inneren Knoten der Tiefe d(T) – 1 zu beginnen.

Prozedur buildheap

Eingabe:

(Fast) vollständiger binärer Baum T mit Knotenmarkierung a

Ausgabe:

Heap (durch Umordnung der Knotenmarken)

Methode:

für i = d(T) – 1 abwärts bis 0 wiederhole

für alle inneren Knoten v der Tiefe d(v) = i wiederhole

downheap(v)

Simulation buildheap

Folgende Simulation veranschaulicht, wie ein (fast) vollständiger binärer Baum mittels buildheap zu einem Heap gemacht wird:

für alle inneren Knoten v wiederhole (bottom-up)

downheap(v)

Der folgende Algorithmus Heapsort konstruiert zunächst mittels buildheap aus den zu sortierenden Elementen einen Heap. Anschließend werden die Elemente in absteigender Reihenfolge ausgegeben, indem wie oben beschrieben jeweils die Markierung der Wurzel ausgegeben, durch die Markierung eines Blattes maximaler Tiefe ersetzt, das Blatt gelöscht und mit downheap die Heap-Struktur wiederhergestellt wird.

Algorithmus Heapsort

Eingabe:

(Fast) vollständiger binärer Baum mit Wurzel r und Knotenmarkierung a

Ausgabe:

Absteigend sortierte Folge der Knotenmarken

Methode:

buildheap

solange r kein Blatt ist wiederhole

gib a(r) aus

wähle Blatt b maximaler Tiefe

markiere r mit a(b)

lösche Blatt b

downheap(r)

gib a(r) aus

Simulation Heapsort

In der Simulation des Heapsort-Algorithmus werden die Knotenmarkierungen innerhalb des binären Baums so umgeordnet, dass dieser zum Schluss die sortierte Folge enthält.

Ein (fast) vollständiger binärer Baum mit n Knoten hat die Tiefe d ≤ log(n). Die Prozedur downheap benötigt daher höchstens log(n) Schritte.

Eine grobe Analyse ergibt, dass buildheap für höchstens n Knoten downheap aufruft. Heapsort ruft zusätzlich noch einmal für alle n Knoten downheap auf. Somit liegt die Zeitkomplexität von Heapsort in O(n·log(n)).

Eine genauere Analyse zeigt, dass buildheap sogar nur O(n) Schritte benötigt. Denn im Verlauf der bottom-up-Konstruktion des Heaps wird downheap für höchstens n/2 Bäume der Tiefe 1, für höchstens n/4 Bäume der Tiefe 2 usw. und schließlich für einen Baum der Tiefe log(n) aufgerufen.

Somit benötigt buildheap höchstens

S = n/2·1 + n/4·2 + n/8·3 + ... + 2·(log(n)-1) + 1·log(n)

Schritte. Da

2S = n·1 + n/2·2 + n/4·3 + n/8·4 + ... + 2·log(n),

ergibt sich durch Subtraktion 2S – S :

S = n + n/2 + n/4 + n/8 + ... + 2 – log(n) .

Somit ist

S ≤ 2n ∈ O(n).

Insgesamt beträgt die Zeitkomplexität von Heapsort allerdings trotzdem noch T(n) ∈ O(n log(n)). Asymptotisch geht es nicht schneller, denn die untere Schranke für das Sortieren liegt bei Ω(n log(n)). Heapsort ist damit optimal, da es die untere Schranke erreicht.

In einem Array a lässt sich ein (fast) vollständiger binärer Baum mit n Knoten und Knotenmarkierung sehr elegant speichern (Bild 3):

die Wurzel steht an Position 0;
die beiden Nachfolger des Knotens an Position v stehen an den Positionen 2v+1 und 2v+2.

Alle Knoten an den Positionen 0, ..., n div 2 – 1 sind innere Knoten, alle Knoten an den Positionen n div 2, ..., n – 1 sind Blätter (div bezeichnet die ganzzahlige Division).

Array-Repräsentation eines Heaps

Bild 3: Array-Repräsentation des Heaps von Bild 1

Die folgende Klasse HeapSorter kapselt die Funktionen downheap, buildheap und heapsort. Die Methode sort übergibt das zu sortierende Array an das Array a und ruft heapsort auf.

In der hier angegebenen Implementierung der Funktion heapsort wird die jeweilige Knotenmarke der Wurzel nicht ausgegeben, sondern mit der Knotenmarke des zu löschenden Blattes vertauscht. Das Blatt wird "gelöscht", indem die Anzahl der noch zu berücksichtigenden Knoten n um 1 vermindert wird. Auf diese Weise steht zum Schluss die aufsteigend sortierte Folge im Array.

Mit der Anweisung

HeapSorter s=new HeapSorter();

wird ein Objekt vom Typ HeapSorter erzeugt; danach kann mit

s.sort(b);

ein Array b sortiert werden. Es folgt das Programm.

public class HeapSorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        heapsort();
    }

    private void heapsort()
    {
        buildheap();
        while (n>1)
        {
            n--;
            exchange(0, n);
            downheap(0);
        }
    }

    private void buildheap()
    {
        for (int v=n/2-1; v>=0; v--)
            downheap(v);
    }

    private void downheap(int v)
    {
        int w=2*v+1;         // erster Nachfolger von v
        while (w<n)
        {
            if (w+1<n)       // gibt es einen zweiten Nachfolger?
                if (a[w+1]>a[w]) w++;
            // w ist der Nachfolger von v mit maximaler Markierung

            if (a[v]>=a[w]) return;  // v hat die Heap-Eigenschaft
            // sonst
            exchange(v, w);  // vertausche Markierungen von v und w
            v=w;             // fahre mit v=w fort
            w=2*v+1;
        }
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class HeapSorter

Mit der Komplexität von Θ(n log(n)) ist Heapsort optimal. Dennoch ist Quicksort im Allgemeinen schneller als Heapsort. Die Variante Bottomup-Heapsort [Weg 93] spart gegenüber Standard-Heapsort etwa die Hälfte der Vergleiche ein.

Standard-Heapsort trägt nach dem Entnehmen des größten Elementes an der Wurzel die Markierung des letzten Blattes als neuen Wert an die freigewordene Position ein. Dieser Wert wird dann bei der Reorganisation des Heaps mit downheap wieder auf eine der (höchstwahrscheinlich) untersten Schichten durchgereicht. In jeder Schicht werden zwei Vergleiche durchgeführt. Einer der Vergleiche dient jeweils dazu, zu ermitteln, ob der durchgereichte Wert schon die richtige Position erreicht hat. Dies wird jedoch im Allgemeinen zunächst nicht der Fall sein, da der Wert von einem Blatt stammt und daher klein ist.

Demgegenüber reicht Bottomup-Heapsort als erstes die freigewordene Position ganz nach unten durch. Hierfür ist nur ein Vergleich pro Schicht erforderlich. Dann wird die Markierung des letzten Blattes in die freigewordene Position eingetragen. Mithilfe der Prozedur upheap muss der Wert dann wieder so weit aufrücken, bis die Heap-Eigenschaft wiederhergestellt ist. Da jedoch die Markierung des letzten Blattes im Allgemeinen ein sehr kleiner Wert ist, sind hierfür, wenn überhaupt, nur wenige Schritte erforderlich.

Die folgenden Bilder zeigen die unterschiedlichen Vorgehensweisen. Bild 4 zeigt, wie Standard-Heapsort den neuen Wert von der Wurzel bis zu seiner richtigen Position durchreicht.

Bild 5 zeigt, wie Bottomup-Heapsort zunächst die an der Wurzel freigewordene Position bis ganz nach unten durchreicht (a) und wie der neue Wert dann gegebenenfalls wieder ein wenig aufrücken muss (b).

neuen Wert nach unten durchreichen

Bild 4: Neuorganisieren des Heaps bei Standard-Heapsort

freigewordene Position nach unten durchreichen neuen Wert eintragen und aufrücken lassen

Bild 5: Neuorganisieren des Heaps bei Bottomup-Heapsort

Simulation Bottomup-Heapsort

In der Simulation des Bottomup-Heapsort-Algorithmus werden die Knotenmarkierungen innerhalb des binären Baums so umgeordnet, dass dieser zum Schluss die sortierte Folge enthält.

Programm

Folgende Klasse BottomupHeapSorter stellt eine mögliche Implementierung der Idee von Bottomup-Heapsort dar. Die Funktionen downheap und buildheap sind dieselben wie in der Klasse HeapSorter.

public class BottomupHeapSorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        bottomupheapsort();
    }

    private void bottomupheapsort()
    {
        int x, u;
        buildheap();
        while (n>1)
        {
            n--;
            x=a[n];    // Markierung des letzten Blatts
            a[n]=a[0];
            u=holedownheap();
            upheap(u, x);
        }
    }

    private void buildheap()
    {
        for (int v=n/2-1; v>=0; v--)
            downheap (v);
    }

    private void downheap(int v)
    {
        int w=2*v+1;         // erster Nachfolger von v
        while (w<n)
        {
            if (w+1<n)       // gibt es einen zweiten Nachfolger?
                if (a[w+1]>a[w]) w++;
            // w ist der Nachfolger von v mit maximaler Markierung

            if (a[v]>=a[w]) return;  // v hat die Heap-Eigenschaft
            // sonst
            exchange(v, w);  // vertausche Markierungen von v und w
            v=w;             // fahre mit v=w fort
            w=2*v+1;
        }
    }

    private int holedownheap()
    {
        int v=0, w=2*v+1;

        while (w+1<n)     // zweiter Nachfolger existiert
        {
            if (a[w+1]>a[w]) w++;
            // w ist der Nachfolger von v mit maximaler Markierung
            a[v]=a[w];
            v=w; w=2*v+1;
        }

        if (w<n)    // einzelnes Blatt
        {
            a[v]=a[w];
            v=w;
        }
        // freigewordene Position ist an einem Blatt angekommen
        return v;
    }

    private void upheap(int v, int x)
    {
        int u;
        a[v]=x;
        while (v>0)
        {
            u=(v-1)/2;    // Vorgänger
            if (a[u]>=a[v]) return;
            // sonst
            exchange(u, v);
            v=u;
        }
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class BottomupHeapSorter

Mit der Zeitkomplexität von O(n log(n)) im schlechtesten Fall ist Heapsort optimal. Im Gegensatz zu Mergesort benötigt Heapsort keinen zusätzlichen Speicherplatz.

Gegenüber Quicksort ist Heapsort im Durchschnitt langsamer. Die Variante Bottomup-Heapsort kommt jedoch der Laufzeit von Quicksort sehr nahe.

Die Datenstruktur des Heaps wird auch zur effizienten Implementation einer Prioritätenliste (engl.: priority queue) benutzt.

Heapsort wurde 1964 von Williams in der Rubrik Algorithms der Zeitschrift Communications of the ACM angegeben [Wil 64].

[AHU 74] A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)

[Sed 88] R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)

[Weg 93] I. Wegener: Bottom-Up-Heapsort, a New Variant of Heapsort Beating on Average Quicksort (if n is not very small). Theoretical Computer Science, 118, 81-98 (1993)

[Wil 64] J.W.J. Williams: Algorithm 232: Heapsort. Communications of the ACM, 7, 6, 347-348 (1964)

[Lan 12] H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Heapsort und andere Sortierverfahren, so etwa Quicksort, Mergesort und Shellsort, finden Sie auch in meinem Buch über Algorithmen.
Weitere (vertikaler Abstand) Themen des Buches: Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

¹) Die Bezeichnung Heap wird auch für den Speicherplatz verwendet, den ein Computer für dynamisch erzeugte Variablen benutzt. Die beiden Begriffe haben jedoch inhaltlich nichts miteinander zu tun.

Weiter mit: [Mergesort] oder [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 25.02.1997 Updated: 23.03.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Sortierverfahren

Heapsort

Grundlagen