Heap-Vorrangwarteschlange (Algorithmus 2.6)

So geht’s: Hier wird nicht sortiert, sondern bedient: Oben eine Zahl mit insert einfügen, eine Zufallszahl einfügen oder mit delMax() das Maximum entnehmen. Jede Operation läuft danach Schritt für Schritt ab, vor und zurück. Derselbe Heap steht zweimal da: als Baum (die kleine Zahl unter jedem Knoten ist sein Platz im Array) und als Array pq[0..15] darunter. So sieht man, dass Kind und Elternknoten nur Indexrechnung sind. Orange ist das Element, das auf- oder absteigt, blau sein Vergleichspartner, grün ein Tausch. „Alle entnehmen“ leert den Heap mit lauter delMax(). Die Zahlen kommen absteigend sortiert heraus, das ist schon die Idee von Heapsort. Der Heap fasst 15 Elemente, also vier Ebenen.

Erklärung

Heap-Vorrangwarteschlange (Algorithmus 2.6) ist streng genommen kein Sortierverfahren, sondern eine Datenstruktur: Man kann beliebig Elemente einfügen und jederzeit das größte herausnehmen. Sie ist aber die Grundlage für Heapsort (Algorithmus 2.7).

Der Heap:

• Ein vollständiger Binärbaum, gespeichert in einem Array pq[1..N]. pq[0] bleibt leer, weil die Rechnung dann aufgeht.
• Zu Knoten k gehören die Kinder 2k und 2k+1, der Elternknoten ist k/2. Keine Zeiger nötig, nur Indexrechnung.
• Heap-Ordnung: Jeder Elternknoten ist ≥ seinen Kindern. Damit steht das Maximum immer in pq[1], der Wurzel.

Die Operationen:

• insert(v): Neues Element hinten anhängen (pq[++N] = v), dann swim(N): Es steigt nach oben, solange es größer als sein Elternknoten ist.
• delMax(): Wurzel pq[1] merken, mit dem letzten Element tauschen, N verkleinern, dann sink(1): Das neue Wurzelelement sinkt ab, indem es jeweils mit dem größeren Kind getauscht wird, bis die Ordnung wieder stimmt.
• pq[N+1] = null: Verhindert Loitering, also dass eine nicht mehr gebrauchte Referenz im Array hängen bleibt und der Garbage Collector den Speicher nicht freigeben kann.

Kosten:

• insert: höchstens 1 + lg N Vergleiche.
• delMax: höchstens 2 lg N Vergleiche (pro Ebene zwei: welches Kind ist größer, und ist es größer als der Knoten).
• Beides logarithmisch, weil der Baum nur lg N Ebenen hat. Eine sortierte oder unsortierte Liste würde bei einer der beiden Operationen N kosten.

Weg zu Heapsort: N Elemente einfügen, dann N-mal delMax, und sie kommen sortiert heraus. Heapsort macht genau das, aber direkt im Eingabearray, ohne Zusatzspeicher, mit garantiert ~2 N lg N Vergleichen.