Sortierverfahren

Heapsort

 English version  aufwärts

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.1) 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.

Grundlagen

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

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

 für alle v Element V  :  (u, vElement E  folgt  a(u)größer gleicha(v) .

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

 für alle (u, vElement E  :  a(u)größer gleicha(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:

 für alle (u, vElement E,  u ≠ r  :  a(u)größer gleicha(v) .

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

Bild 1: Heap mit n = 10 Knoten
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.

Sortierverfahren

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
(a) (b) (c)
Vertauschen der Markierung mit maximaler Markierung der direkten Nachfolger Heap wieder­hergestellt
(d) (e)
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:
  1. solange v nicht die Heap-Eigenschaft hat wiederhole
    1. 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:
  1. für i = d(T) – 1 abwärts bis 0 wiederhole
    1. für alle inneren Knoten v der Tiefe d(v) = i wiederhole
      1. 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:
  1. buildheap

    solange r kein Blatt ist wiederhole

    1. 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

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

 

(Java-Applet zur Simulation der Prozedur buildheap)

Analyse

Ein (fast) vollständiger binärer Baum mit n Knoten hat die Tiefe dkleiner gleichlog(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  kleiner gleich  2n  Element  O(n).

 

Insgesamt beträgt die Zeitkomplexität von Heapsort allerdings trotzdem noch T(nElement 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.

Implementierung

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

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

Programm

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

Variante: Bottomup-Heapsort

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
(a) (b)
Bild 5: Neuorganisieren des Heaps bei Bottomup-Heapsort

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

Zusammenfassung

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.

Literatur

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]

Buch  

1)  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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.02.1997   Updated: 29.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik