Quelltext der Seite Heapsort

[[Datei:Sorting heapsort anim.gif|gerahmt|rechts|Der Heapsort-Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen Sortierschritt kurz eingeblendet wird.]]

'''Heapsort''' („Haldensortierung“) ist ein in den 1960ern von [[Robert W. Floyd]] und [[J.&nbsp;W.&nbsp;J. Williams]] entwickeltes [[Sortierverfahren]]. Seine [[Komplexitätstheorie|Komplexität]] ist bei einem [[Array (Datentyp)|Array]] der Länge <math>n</math> in der [[Landau-Symbole|Landau-Notation]] ausgedrückt in <math> \mathcal{O}(n \cdot \log n) </math> und ist damit asymptotisch optimal für Sortieren per Vergleich. Heapsort arbeitet zwar [[in-place]], ist jedoch nicht [[Stabilität (Sortierverfahren)|stabil]]. Der Heapsort-Algorithmus verwendet einen [[Binärer Heap|binären Heap]] als zentrale [[Datenstruktur]]. Heapsort kann als eine Verbesserung von [[Selectionsort]] verstanden werden und ist mit [[Treesort]] verwandt.

== Beschreibung ==

Die Eingabe ist ein [[Array (Datentyp)|Array]] mit zu sortierenden Elementen. Als erstes wird die Eingabe in einen [[Binärer Heap|binären Max-Heap]] [[Binärer Heap#Build|überführt]]. Aus der [[Binärer Heap#Struktur|Heap-Eigenschaft]] folgt direkt, dass nun an der ersten Array-Position das größte Element steht. Dieses wird mit dem letzten Array-Element vertauscht und die Heap-Array-Größe um 1 verringert, ohne den Speicher freizugeben. Die neue [[Binärbaum|Wurzel]] des Heaps kann die Heap-Eigenschaft verletzen. Die [[Binärer Heap#Heapify|Heapify-Operation]] korrigiert gegebenenfalls den Heap, so dass nun das nächstgrößere bzw. gleich große Element an der ersten Array-Position steht. Die Vertausch-, Verkleiner- und Heapify-Schritte werden so lange wiederholt, bis die Heap-Größe 1 ist. Danach enthält das Eingabe-Array die Elemente in aufsteigend sortierter Reihenfolge. In [[Pseudocode]]:

<syntaxhighlight lang="C">
heapsort(Array A)
  build(A)
  assert(isHeap(A, 0))
  tmp = A.size
  while (A.size > 1)
    A.swap(0, A.size - 1)
    A.size = A.size - 1
    heapify(A)
    assert(isHeap(A, 0))
  A.size = tmp
  assert(isSorted(A))
</syntaxhighlight>

Bei einer Sortierung in absteigender Reihenfolge wird statt des Max-Heaps ein Min-Heap verwendet. In einem Min-Heap steht an erster Stelle das kleinste Element. Gemäß der Definition von einem binären Heap wird die Abfolge der Elemente in einem [[Heap (Datenstruktur)|Heap]] durch eine Vergleichsoperation (siehe [[Ordnungsrelation]]) bestimmt, die eine [[totale Ordnung]] auf den Elementen definiert. In einem Min-Heap ist das die <math><</math>-Relation und in einem Max-Heap die <math>></math>-Relation. Der Pseudocode abstrahiert von der Vergleichsoperation.

Die zu sortierenden Elemente werden auch als [[Nummerung|Schlüssel]] bezeichnet. Pro Index-Position kann das Eingabe-[[Array (Datentyp)|Array]] mehrere Datenkomponenten enthalten. In dem Fall muss eine Komponente als Sortierschlüssel definiert werden, auf der die Vergleichsoperation arbeitet. Die Vertauschoperation vertauscht komplette Array-Einträge.

Die assert-Operation im [[Pseudocode]] dokumentiert, welche Eigenschaften das Array nach welchen [[Algorithmus]]-Schritten korrekterweise erfüllt bzw. erfüllen muss.

== Beispiel ==

[[Datei:Heapsort.svg|600px|zentriert|Ein Beispiel für Heapsort an einer Zahlenfolge]]

In der Abbildung wird die Sortierung der Beispielzahlenfolge

  23 1 6 19 14 18 8 24 15

mit dem Heapsort-Algorithmus dargestellt. Die einzelnen Teilbilder sind von links nach rechts und von oben nach unten chronologisch angeordnet. Im ersten Teilbild ist die unsortierte Eingabe und im letzten die sortierte Ausgabe abgebildet. Der Übergang vom ersten zum zweiten Teilbild entspricht der Heapifizierung des Eingabe-Arrays. Die an einer Swap-Operation beteiligten Elemente sind rot und mit unterbrochenen Pfeilen markiert, dicke Doppelpfeile bezeichnen die an einer Heapify-Operation beteiligten Elemente und grün markierte Elemente zeigen den schon sortierten Anteil des Arrays an. Die Element-Indizes sind mit kleinen schwarzen Knoten eingezeichnet, jeweils links unten von dem Element-Wert. Eine blaue Hinterlegung der Array-Elemente indiziert die Laufzeit der Heapsort-Prozedur.

Die Indizes entsprechen einer aufsteigenden Nummerierung nach Level-Order, beginnend mit 0. In einer Implementierung des Algorithmus ist die Baumstruktur implizit und das Array der Elemente zusammenhängend, was durch die Platzierung der Element-Indizes in der Abbildung angedeutet wird.

== Effizienz ==

Man kann zeigen, dass der [[Binärer Heap#Build|Aufbau des Heaps]], in [[Landau-Notation]] ausgedrückt, in <math> \mathcal{O}(n) </math> Schritten ablaufen kann. In einem großen, zufällig verteilten Datenfeld (100 bis 10<sup>10</sup> Datenelemente) sind durchschnittlich mehr als 4, aber weniger als 5 signifikante Sortieroperationen pro Element nötig (2,5 Datenvergleiche und 2,5 Zuweisungen). Dies liegt daran, dass ein zufälliges Element mit exponentiell zunehmender Wahrscheinlichkeit einen geeigneten Vaterknoten findet (60 %, 85 %, 93 %, 97 %, …).

Die [[Binärer Heap#Heapify|Heapify-Operation]] benötigt im [[Worst Case|ungünstigsten Fall]] <math> \Theta(\log n) </math> Schritte. Dies ist bei exakt inverser Reihenfolge der Fall. In dem durchschnittlichen Fall werden etwa die Hälfte der Operationen des ungünstigsten Falls und somit ebenfalls <math> \Theta(\log n) </math> Schritte benötigt. Günstig ist nur ein Feld, dessen Elemente fast alle den gleichen Wert haben. Sind aber nur weniger als ca. 80 % der Daten identisch, dann entspricht die Laufzeit bereits dem durchschnittlichen Fall. Eine vorteilhafte Anordnung von Daten mit mehreren verschiedenen Werten ist prinzipbedingt unmöglich, da dies der Heapcharakteristik widerspricht.

Den [[Worst Case]] stellen mit <math> \Theta(n \cdot \log n) </math> weitgehend vorsortierte Daten dar, weil der Heapaufbau de facto eine schrittweise vollständige Invertierung der Sortierreihenfolge darstellt. Der günstigste, aber unwahrscheinliche Fall ist ein bereits umgekehrt sortiertes Datenfeld (1 Vergleich pro Element, keine Zuweisung). Gleiches gilt, wenn fast alle Daten identisch sind.

Auf heterogenen Daten – vorsortiert oder nicht – dominiert Heapify mit wenigstens über 60 % der Zeit, meistens über 80 %. Somit garantiert Heapsort eine [[Laufzeit (Informatik)|Gesamtlaufzeit]] von <math>\mathcal{O}(n \cdot \log n) </math>. Auch im besten Fall wird eine Laufzeit von <math> \Theta(n \cdot \log n) </math> benötigt.<ref>Russel Schaffer, Robert Sedgewick: ''The analysis of heapsort.'' In: ''Journal of Algorithms,'' Volume 15,  Issue 1. Juli 1993. S. 76–100, {{ISSN|0196-6774}}</ref><ref>Bela Bollobas, Trevor I. Fenner, Alan M. Frieze: ''On the best case of heapsort.'' In: ''Journal of Algorithms,'' Volume 20,  Issue 2. März 1996. S. 205–217. {{ISSN|0196-6774}}</ref>

Eine Variante von Heapsort benötigt im [[Worst Case]] <math>n\cdot\log_{2}(n)+n\cdot\log_{2}(\log_{2}(n)) + n</math> Vergleiche.<ref>Gu Xunrang, Zhu Yuzhang: [https://www.sciencedirect.com/science/article/pii/0304397595002332 Optimal heapsort algorithm]</ref>

== Abgrenzung ==

Im Durchschnitt ist Heapsort nur dann schneller als [[Quicksort]], wenn Vergleiche auf den zu sortierenden Daten sehr aufwendig sind und gleichzeitig eine für Quicksort ungünstige Datenanordnung besteht, z.&nbsp;B. viele gleiche Elemente. In der Praxis ist bei unsortierten oder teilweise vorsortierten Daten Quicksort oder [[Introsort]] um einen konstanten Faktor von 2 bis 5 schneller als Heapsort. Dies wird jedoch kontrovers diskutiert und es gibt Analysen, die Heapsort vorne sehen, sowohl aus Implementierungs- wie auch aus informationstheoretischen Überlegungen.<ref>{{cite web| first=Paul |last=Hsieh| title=Sorting revisited.| url=http://www.azillionmonkeys.com/qed/sort.html| date=2004| publisher = azillionmonkeys.com |language=en |accessdate=2024-10-25}}</ref><ref>{{cite web| first=David |last=MacKay| title=Heapsort, Quicksort, and Entropy |language=en | url=http://www.aims.ac.za/~mackay/sorting/sorting.html| archiveurl=https://web.archive.org/web/20070607172645/http://www.aims.ac.za/~mackay/sorting/sorting.html| archivedate=2007-06-07| date=2005-12-01 | accessdate=2010-04-26| publisher = aims.ac.za/~mackay}}</ref> Allerdings spricht das [[Worst Case|Worst-Case]]-Verhalten von <math> \mathcal{O}(n \cdot \log n) </math> gegenüber <math> \Theta(n^2 ) </math> bei Quicksort für Heapsort. Introsort ist dagegen in fast allen Fällen schneller als Heapsort, lediglich in entarteten Fällen 20 % bis 30 % langsamer.

== Bottom-Up-Heapsort ==

Die wichtigste Variante des Heapsort-Algorithmus ist [[Bottom-Up-Heapsort]], das häufig fast die Hälfte der nötigen Vergleichsoperationen einsparen kann und sich folglich besonders da rentiert, wo Vergleiche aufwendig sind.

Bottom-Up-Heapsort ist ein [[Sortierverfahren|Sortieralgorithmus]], der u. a. [[1990]] von [[Ingo Wegener]] vorgestellt wurde und im Durchschnitt besser als [[Quicksort]] arbeitet, falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von Heapsort, die vor allem zur Sortierung sehr großer Datenmengen geeignet ist, wenn (im Vergleich zu den notwendigen Vertauschungsoperationen) ein relativ hoher Aufwand pro Vergleichsoperation erforderlich ist.

Diese Variante wurde allerdings bereits [[1986]] von Svante Carlsson analysiert, der letztlich eine weitere Variante fand, die sogar eine [[Worst Case|Worst-Case]]-[[Laufzeit (Informatik)|Laufzeit]] von nur <math>n\cdot\log_{2}(n) + \mathcal{O}(n \cdot \log_{2}(\log_{2}(n)))</math> Vergleichen hat. Entdeckt wurde dieser Bottom-Up-Heapsort bereits von [[Robert Floyd|Robert W Floyd]], der aber das Laufzeitverhalten dieser Variante nicht beweisen konnte.

Bottom-Up-Heapsort benötigt zum Sortieren einer Folge von <math>n</math> Elementen im [[Worst Case]] <math>\tfrac{3}{2}\cdot n\cdot\log_{2}(n) + 2\cdot n</math> Vergleiche. Im Durchschnitt sind es <math>n\cdot\log_{2}(n) + \mathcal{O}(n)</math> Vergleiche.

=== Prinzip der Sortierung ===
Beim Sortieren mit normalem Heapsort finden beim Absenken eines Elements zwei Vergleiche pro Ebene statt:

# Welcher der beiden Nachfolgeknoten des abzusenkenden Elements ist größer?
# Ist der nun bestimmte Nachfolgeknoten größer als das abzusenkende Element?

Nachdem ein [[Binärbaum]] zur Hälfte aus [[Blätter und innere Knoten in der Graphentheorie|Blättern]] besteht und zudem beim Sortieren ehemalige Blätter mit ohnehin schon eher niedrigen Werten abgesenkt werden, ist es wahrscheinlich, dass ein Element bis zur Blattebene oder in deren Nähe abgesenkt werden muss. Deshalb kann es lohnend sein, auf den zweiten Vergleich zu verzichten und auf Verdacht bis zur Blattebene abzusenken.

In einem zweiten Schritt wird dann rückwärts überprüft, wie weit das Element wieder angehoben werden muss. Im günstigsten Fall (sehr große Felder mit nur wenigen [[Dublette (Datenbank)|Dubletten]]) kann dabei fast die Hälfte der insgesamt nötigen Vergleiche bei mäßigem Zusatzaufwand eingespart werden.

Weniger geeignet ist Bottom-Up-Heapsort zur Sortierung kleinerer Felder mit einfacher numerischer Vergleichsoperation und dann, wenn im Feld sehr viele Elemente gleichwertig sind. Dann stimmt die Annahme nicht, dass meist bis in die Nähe der Blattebene abgesenkt werden muss.

=== Algorithmus ===
Konkret wird der Heapsort-Algorithmus, was das Absenken betrifft, wie folgt verändert:

Zunächst wird der [[Weg (Graphentheorie)|Pfad]], in welchem das [[Wurzel (Graphentheorie)|Wurzelelement]] versenkt werden soll, bestimmt. Dies geschieht durch die Ermittlung des jeweils größten Kindes (Pfad maximaler Kinder). Danach wird dieser bestimmte Pfad von unten nach oben vom Blatt in Richtung Wurzel durchlaufen. Hierbei wird bei jedem besuchten Knoten verglichen, ob er größer als das abzusenkende Wurzelelement ist. Ist dem so, wird das Wurzelelement an die Position des zuletzt besuchten Knotens kopiert und vorher der restliche Pfad um eine Ebene nach oben verschoben.

Alternativ kann man auch die Verschiebung von vornherein auf Verdacht bis zur Blattebene durchführen und später – soweit notwendig – wieder rückgängig machen. Wo Kopien relativ günstig durchgeführt werden können (weil etwa nur ein [[Zeiger (Informatik)|Zeiger]] kopiert wird), kann das insgesamt vorteilhaft sein.

=== Beispiel ===
'''Heap''': [9, 23, 24, 20, 18, 14, 17, 13, 15, 11, 10, 5, 7, 3, 2]

'''Baumstruktur:'''
             9
        /         \
       23         24
     /   \       /  \
    20   18     14  17
   / \   / \   / \  / \
  13 15 11 10  5  7 3  2
Das Element '''9''' muss abgesenkt werden, da es kleiner als mindestens ein Nachfolgeknoten ist. Es wird als erstes der Pfad der maximalen Kinder (ausgehend von der Wurzel) bestimmt. Es ergibt sich also '''9 - 24 - 17 - 3'''. Der Algorithmus durchläuft diesen Pfad nun von unten nach oben, also '''3 -> 17 -> 24 -> 9'''. Nun wird der Pfad vom Blattknoten '''(3)''' beginnend solange durchlaufen, bis sich ein Knoten findet, der größer als '''9''' ist. Der Durchlauf endet folglich bei '''17'''. Nun werden alle Knoten ab '''17''' bis zum Nachfolgeknoten der Wurzel '''(= 17 -> 24)''' um eine Ebene nach oben und der Knoten '''9''' an die Position von '''17''' verschoben. Folglich ändern '''17''' und '''24''' als Nachfolgeknoten und '''9''' als Wurzelknoten ihren Platz.

'''Heap''': [24, 23, 17, 20, 18, 14, 9, 13, 15, 11, 10, 5, 7, 3, 2]

'''Baumstruktur:'''
            24           -------|                      24
        /         \             |                 /         \
       23         17            9                23         17
     /   \       /  \           |               /   \      /   \
    20   18     14      <-------|              20   18    14    9
   / \   / \   / \  / \                       / \   / \   / \  / \
  13 15 11 10  5  7 3  2                     13 15 11 10 5  7  3  2

=== Implementierung ===
Einfache Beispielsimplementierung in der [[C (Programmiersprache)|Programmiersprache C]]:<syntaxhighlight lang="C">
 int heapsort_bu( int * data, int n ) // zu sortierendes Feld und seine Länge
 {
   int val, parent, child;
   int root= n >> 1;                  // erstes Blatt im Baum
   int count= 0;                      // Zähler für Anzahl der Vergleiche

   for ( ; ; )
   {
     if ( root ) {                    // Teil 1: Konstruktion des Heaps
       parent= --root;
       val= data[root];               // zu versickernder Wert
     }
     else
     if ( --n ) {                     // Teil 2: eigentliche Sortierung
       val= data[n];                  // zu versickernder Wert vom Heap-Ende
       data[n]= data[0];              // Spitze des Heaps hinter den Heap in
       parent= 0;                     //   den sortierten Bereich verschieben
     }
     else                             // Heap ist leer; Sortierung beendet
       break;

     while ( (child= (parent + 1) << 1) < n )  // zweites (!) Kind;
     {                                         // Abbruch am Ende des Heaps
       if ( ++count, data[child-1] > data[child] )  // größeres Kind wählen
         --child;

       data[parent]= data[child];     // größeres Kind nach oben rücken
       parent= child;                 // in der Ebene darunter weitersuchen
     }

     if ( child == n )                // ein einzelnes Kind am Heap-Ende
     {                                //   ist übersprungen worden
       if ( ++count, data[--child] >= val ) {  // größer als der zu versick-
         data[parent]= data[child];   //   ernde Wert, also noch nach oben
         data[child]= val;            // versickerten Wert eintragen
         continue;
       }

       child= parent;                 // 1 Ebene nach oben zurück
     }
     else
     {
       if ( ++count, data[parent] >= val ) {  // das Blatt ist größer als der
         data[parent]= val;           //   zu versickernde Wert, der damit
         continue;                    //   direkt eingetragen werden kann
       }

       child= (parent - 1) >> 1;      // 2 Ebenen nach oben zurück
     }

     while ( child != root )          // maximal zum Ausgangspunkt zurück
     {
       parent= (child - 1) >> 1;      // den Vergleichswert haben wir bereits
                                      //   nach oben verschoben
       if ( ++count, data[parent] >= val )  // größer als der zu versickernde
         break;                             //   Wert, also Position gefunden

       data[child]= data[parent];     // Rückverschiebung nötig
       child= parent;                 // 1 Ebene nach oben zurück
     }

     data[child]= val;                // versickerten Wert eintragen
   }

   return count;
 }
</syntaxhighlight>Zu Vergleichszwecken gibt die Funktion die Anzahl der durchgeführten Vergleiche zurück.

== Andere Varianten ==

=== Smoothsort ===

Normales Heapsort sortiert bereits weitgehend vorsortierte Felder nicht schneller als andere. Die größten Elemente müssen immer erst ganz nach vorn an die Spitze des Heaps wandern, bevor sie wieder nach hinten kopiert werden. [[Smoothsort]] ändert das, indem es im Prinzip die Reihenfolge des Heaps umdreht. Dabei ist allerdings beträchtlicher Aufwand nötig, um den Heapstatus beim Sortieren aufrechtzuerhalten. Smoothsort benötigt eine lineare [[Laufzeit (Informatik)|Laufzeit]] von <math> \mathcal{O}(n) </math>, um ein vorsortiertes Array ([[Best Case]]) zu verarbeiten, und genauso wie andere Varianten eine Laufzeit von <math> \mathcal{O}(n \cdot \log n) </math> im Durchschnitt und im [[Worst Case]], und erzielt bei vielen nahezu sortierten Eingaben eine nahezu lineare Leistung. Es werden jedoch nicht alle nahezu sortierten Sequenzen optimal verarbeitet.<ref>{{cite journal|last=Hertel|first=Stefan|title=Smoothsort’s behavior on presorted sequences|journal=[[Information Processing Letters]]|volume=16|issue=4|date=1983-05-13|pages=165–170|url=https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/26149|format=PDF|doi=10.1016/0020-0190(83)90116-3}}</ref>

=== Ternäre Heaps ===

Eine andere Optimierung verwendet statt binären ternäre [[Heap (Datenstruktur)|Heaps]]. Diese Heaps beruhen statt auf [[Binärbaum|Binärbäumen]] auf Bäumen, bei denen jeder vollständig besetzte Knoten 3 Kinder hat. Damit kann die Zahl der Vergleichsoperationen bei einigen Tausend bis einigen Millionen Elementen um etwa 3 % reduziert werden. Außerdem sinkt der sonstige Aufwand deutlich. Insbesondere müssen durch den flacheren Heap knapp ein Drittel weniger Elemente beim Versickern (Heapify) verschoben werden.

In einem [[Binärer Heap|binären Heap]] kann ein Element mit <math>2 \cdot n</math> Vergleichen um <math>n</math> Ebenen abgesenkt werden und hat dabei durchschnittlich <math>\tfrac{3}{2} \cdot (2^n - 1)</math> Indizes übersprungen. In einem ternären [[Heap (Datenstruktur)|Heap]] kann ein Element mit <math>3 \cdot m</math> Vergleichen um <math>m</math> Ebenen abgesenkt werden und hat dabei durchschnittlich <math>3^m - 1</math> Indizes übersprungen. Wenn bei gleicher Reichweite der relative Aufwand <math>x := \tfrac{3 \cdot m}{2 \cdot n}</math> ist, dann gilt

:<math>\frac{3}{2} \cdot (2^n - 1) = 3^{\frac{2 \cdot n \cdot x}{3}}-1</math>, also <math>x = \frac{3}{2 \cdot n} \cdot \log_3\left(\frac{3}{2} \cdot 2^n - \frac{1}{2}\right) =_{n\to\infty} \frac{3}{2} \cdot \log_3(2) \approx 0{,}946</math>

Bei <math>n=18</math> (realistisch bei knapp 1 Million Elementen) ergibt sich 0,977. Die 1 wird oberhalb von <math>n=10</math> unterschritten. In der Praxis ist die Ersparnis etwas größer, u.&nbsp;a. deswegen, weil ternäre Bäume mehr Blätter haben und deshalb beim Aufbau des [[Heap (Datenstruktur)|Heaps]] weniger Elemente versickert werden müssen.

Insgesamt kann die Sortierung mit ternären Heaps bei großen Feldern (mehrere Millionen Elemente) und einfacher Vergleichsoperation 20 % bis 30 % Zeit einsparen. Bei kleinen Feldern (bis etwa tausend Elemente) lohnen sich ternäre Heaps nicht oder sind sogar langsamer.

=== ''n''-äre Heaps ===

Bei noch breiteren [[Baum (Graphentheorie)|Bäumen]] bzw. flacheren [[Heap (Datenstruktur)|Heaps]] steigt die Zahl der nötigen Vergleichsoperationen wieder an. Trotzdem können sie vorteilhaft sein, weil der sonstige Aufwand vor allem der für das Kopieren von Elementen weiter sinkt und geordneter auf die Elemente zugegriffen wird, was die Effizienz von [[Cache]]s erhöhen kann. Sofern bei großen Feldern nur ein einfacher numerischer Vergleich durchzuführen ist und Schreiboperationen relativ langsam sind, können 8 oder mehr Kinder pro Knoten optimal sein.

Einfache Beispielsimplementierung mit Heaps beliebiger [[Arität]] (WIDTH, mit WIDTH>=2) in der [[C (Programmiersprache)|Programmiersprache C]]:
<syntaxhighlight lang="c">
static size_t heapify(int *data, size_t n, size_t WIDTH, size_t root)
{
  assert(root < n);
  size_t count = 0;
  int val = data[root];
  size_t parent = root;
  size_t child = 0;
  assert(parent * WIDTH >= parent); // Overflow-Test
  while ( (child = parent * WIDTH + 1) < n )  // erstes Kind;
  {                                           // Abbruch am Ende des Heaps
    size_t w = n - child < WIDTH ?
      n - child : WIDTH;            // Anzahl der vorhandenen Geschwister

    count += w;

    size_t max = 0;
    for (size_t i = 1; i < w; ++i )  // größtes Kind suchen
      if (data[child+i] > data[child+max])
        max = i;
    child += max;

    if (data[child] <= val)        // kein Kind mehr größer als der
      break;                        //   zu versickernde Wert

    data[parent] = data[child];     // größtes Kind nach oben rücken
    parent = child;                 // in der Ebene darunter weitermachen
  }
  data[parent] = val;               // gesiebten Wert eintragen
  return count;
}

size_t nhsort(int * data, size_t n, size_t WIDTH)
{
  assert(WIDTH > 1);
  if (n < 2)
    return 0;
  size_t m = (n + WIDTH - 2) / WIDTH;  // erstes Blatt im Baum
  int count = 0;                       // Zähler für Anzahl der Vergleiche

  assert(m > 0);
  for (size_t r = m; r > 0; --r)       // Teil 1: Konstruktion des Heaps
    count += heapify(data, n, WIDTH, r-1);
  for (size_t i = n - 1; i > 0; --i) { // Teil 2: eigentliche Sortierung
    int tmp = data[0];                 // Spitze des Heaps hinter den Heap in
    data[0] = data[i];
    data[i] = tmp;                     //   den sortierten Bereich verschieben
    count += heapify(data, i, WIDTH, 0);
  }
  return count;
}
</syntaxhighlight>
Zu Vergleichszwecken gibt die Funktion die Anzahl der durchgeführten Vergleiche zurück.

== Siehe auch ==

* [[Hybridsort]]

== Literatur ==

* {{BibISBN|0262032937|Seite=135}}
* {{BibISBN|0201896850|Seite=145}}
* {{Literatur
   |Autor=[[Robert Floyd|Robert W. Floyd]]
   |Titel=Algorithm 245: Treesort 3
   |Sammelwerk=Communications of the ACM
   |Band=7
   |Nummer=12
   |Datum=1964-12
   |Seiten=701}}
* {{Literatur
   |Autor=J. W. J. Williams
   |Titel=Algorithm 232: Heapsort
   |Sammelwerk=Communications of the ACM
   |Band=7
   |Nummer=6
   |Datum=1964-06
   |Seiten=347–348}}
* {{Literatur
   |Autor=[[Robert Floyd|Robert W. Floyd]]
   |Titel=Algorithm 113: Treesort
   |Sammelwerk=Communications of the ACM
   |Band=5
   |Nummer=8
   |Datum=1962-08
   |Seiten=434}}

== Weblinks ==
{{Wikibooks|Algorithmensammlung: Sortierverfahren: Heapsort|Heapsort|suffix=Implementierungen in der Algorithmensammlung}}
{{Commonscat|Heap sort}}
* [http://vimeo.com/2942939 Video zur Visualisierung von Heap Sort] auf vimeo.com
* {{Internetquelle |autor=Hans Werner Lang |url=https://hwlang.de/algorithmen/sortieren/heap/heap.htm |titel=Heapsort |werk=hwlang.de |datum=2023-03-23 |abruf=2024-10-25 |abruf-verborgen=1}}
* [https://www.sortieralgorithmen.de/heapsort/index.html Heaptsort auf sortieralgorithmen.de]
* [https://docs.python.org/3/library/heapq.html Heapsort in Python 3 – Heap queue algorithm] auf docs.python.org

== Einzelnachweise ==
<references />

[[Kategorie:Sortieralgorithmus]]