Heapsort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
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. W. J. Williams entwickeltes Sortierverfahren. Seine Komplexität ist bei einem Array der Länge n in der Landau-Notation ausgedrückt in  \mathcal{O}(n \cdot \log n) und ist damit asymptotisch optimal für Sortieren per Vergleich. Heapsort arbeitet zwar in-place, ist jedoch nicht stabil. Der Heapsort-Algorithmus verwendet einen binären Heap als zentrale Datenstruktur. Heapsort kann als eine Verbesserung von Selectionsort verstanden werden und ist mit Treesort verwandt.

Algorithmus[Bearbeiten]

Die Eingabe ist ein Array mit zu sortierenden Elementen. Als erstes wird die Eingabe in einen binären Max-Heap überführt. Aus der 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 Wurzel des Heaps kann die Heap-Eigenschaft verletzen. Die 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:

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

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 durch eine Vergleichsoperation (mathematisch: Relation) bestimmt, die eine totale Ordnung auf den Elementen definiert. In einem Min-Heap ist das die <-Relation und in einem Max-Heap die >-Relation. Der Pseudocode abstrahiert von der Vergleichsoperation.

Die zu sortierenden Elemente werden auch als (Sortier-)Schlüssel bezeichnet. Pro Index-Position kann das Eingabe-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 für Heapsort mit Zahlen[Bearbeiten]

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[Bearbeiten]

Man kann zeigen, dass der Aufbau des Heaps, in Landau-Notation ausgedrückt, in  \mathcal{O}(n) Schritten ablaufen kann. In einem großen, zufällig verteilten Datenfeld (100 bis 1010 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 Heapify-Operation benötigt im ungünstigsten Fall (Worst Case)  \mathcal{O}(\log n) Schritte. Dies ist bei exakt inverser Reihenfolge der Fall. Durchschnittlicher und ungünstigster Fall unterscheiden sich jedoch praktisch nur unwesentlich:  \mathcal{O}(\log n/2) zu  \mathcal{O}(\log n) . 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  \mathcal{O}(n \cdot \log n) 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 Gesamtlaufzeit von  \mathcal{O}(n \cdot \log n) . Auch im besten Fall wird eine Laufzeit von  \Omega(n \cdot \log n) benötigt.[1][2]

Abgrenzung[Bearbeiten]

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.B. viele gleiche Elemente). In der Praxis ist bei unsortierten oder teilweise vorsortierten Daten Quicksort oder Introsort um einen konstanten Faktor (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.[3][4] Allerdings spricht das Worst-Case-Verhalten von  \mathcal{O}(n \cdot \log n) gegenüber  \mathcal{O}(n^2 ) 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.

Varianten[Bearbeiten]

Bottom-Up-Heapsort[Bearbeiten]

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. (Siehe dort auch die wissenschaftlich entscheidenden Referenzen zu Heapsort.)

Smoothsort[Bearbeiten]

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.

Ternäre Heaps[Bearbeiten]

Eine andere Optimierung verwendet statt binären ternäre Heaps. Diese Heaps beruhen statt auf Binärbäumen auf Bäumen, bei denen jeder vollständig besetzte Knoten 3 Kinder hat. Damit kann die Zahl der Vergleichsoperationen um etwa 3–4% reduziert werden (bei einigen Tausend bis einigen Millionen Elementen). 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ären Heap kann ein Element mit 2n Vergleichen um n Ebenen abgesenkt werden und hat dabei durchschnittlich \frac{3}{2}\cdot(2^n-1) Indizes übersprungen. In einem ternären Heap kann ein Element mit 3m Vergleichen um m Ebenen abgesenkt werden und hat dabei durchschnittlich 3m-1 Indizes übersprungen. Wenn bei gleicher Reichweite der relative Aufwand x := 3m/2n ist, dann gilt

\frac{3}{2}\left(2^n-1\right)=3^{\frac{2n}{3}x}-1, alsox=\frac{3}{2n}\log_3\left(\frac{3}{2}2^n-\frac{1}{2}\right)=_{n\to\infty}\frac{3}{2}\log_3 2 \approx 0{,}946

Bei n=18 (realistisch bei knapp 1 Million Elementen) ergibt sich 0,977; die 1 wird oberhalb von n=10 unterschritten. In der Praxis ist die Ersparnis etwas größer, u.a. deswegen, weil ternäre Bäume mehr Blätter haben und deshalb beim Aufbau des 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–30% Zeit einsparen. Bei kleinen Feldern (bis etwa tausend Elemente) lohnen sich ternäre Heaps nicht oder sind sogar langsamer.

n-äre Heaps[Bearbeiten]

Bei noch breiteren Bäumen bzw. flacheren 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 Caches 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 Programmiersprache 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;
}

Zu Vergleichszwecken gibt die Funktion die Anzahl der durchgeführten Vergleiche zurück.

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Russel Schaffer, Robert Sedgewick: The analysis of heapsort. In: Journal of Algorithms, Volume 15, Issue 1. Juli 1993. S. 76–100, ISSN 0196-6774
  2. 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
  3. Paul Hsieh: Sorting revisited.. www.azillionmonkeys.com. 2004. Abgerufen am 26. April 2010.
  4. David MacKay: Heapsort, Quicksort, and Entropy. www.aims.ac.za/~mackay. 1. Dezember 2005. Archiviert vom Original am 7. Juni 2007. Abgerufen am 26. April 2010.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

 Wikibooks: Heapsort – Implementierungen in der Algorithmensammlung
 Commons: Heap sort – Sammlung von Bildern, Videos und Audiodateien