Der Heapsort-Algorithmus

Merge Sort garantiert O(n log n) mithilfe eines zusätzlichen Arrays. Heapsort gibt dieselbe Garantie in-place, ganz ohne zweites Array, indem es sich eine Datenstruktur borgt, die man sonst eher mit Priority Queues verbindet: den binären Heap.

Die Idee

Ein binärer Heap, der in einem einfachen Array gespeichert wird, nutzt Arithmetik statt Zeiger: Für jeden Index i liegen seine Kinder bei 2i + 1 und 2i + 2. Ein Max-Heap hält überall in diesem impliziten Baum eine Invariante ein: Jedes Elternelement ist größer oder gleich beiden seinen Kindern — was den einzigen größten Wert an die Wurzel, Index 0, zwingt, aber nichts über die Reihenfolge des Rests aussagt.

Heapsort arbeitet in zwei Phasen. Zuerst wird aus dem gesamten Array ein Max-Heap aufgebaut — eine beliebige Anordnung wird in eine umgewandelt, die die Heap-Invariante überall erfüllt, ohne dabei schon irgendetwas vollständig zu sortieren. Danach wird wiederholt das Maximum extrahiert: Die Wurzel ist immer der größte verbleibende Wert, also wird sie ans Ende des noch unsortierten Bereichs getauscht, der Heap um eins verkleinert, und die Heap-Invariante an der Wurzel wiederhergestellt. Das einmal pro verbleibendem Element zu tun sortiert das gesamte Array, vom größten zum letzten, eine Extraktion nach der anderen.

Beide Phasen beruhen auf derselben Operation: Sift Down (Versickern). Verletzt ein Knoten möglicherweise die Heap-Invariante gegenüber seinen Kindern, wird er mit beiden verglichen, mit dem größeren Kind getauscht, falls eines größer ist, und das an der neuen Position wiederholt — den Baum hinab, nie zurück nach oben — bis der Knoten entweder ein Blatt ist oder größer als beide seine Kinder.

Implementierung

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
bool settled[N];

int heapSize = N;
int buildIndex = N / 2 - 1;
bool building = true;
int extractEnd = N - 1;
int cur = -1;   // node currently being sifted down; -1 = need the next task
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
        settled[n] = false;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (cur == -1) {
            if (building) {
                if (buildIndex >= 0) {
                    cur = buildIndex;
                    buildIndex--;
                } else {
                    building = false; // heap property established, extract next
                }
            } else if (extractEnd <= 0) {
                done = true;
            } else {
                int tmp = values[0];
                values[0] = values[extractEnd];
                values[extractEnd] = tmp;
                settled[extractEnd] = true; // max of the remaining heap, now final
                heapSize = extractEnd;
                extractEnd--;
                cur = 0;
            }
        } else {
            int left = 2 * cur + 1;
            int right = 2 * cur + 2;
            int largest = cur;
            if (left < heapSize && values[left] > values[largest]) largest = left;
            if (right < heapSize && values[right] > values[largest]) largest = right;

            if (largest != cur) {
                int tmp = values[cur];
                values[cur] = values[largest];
                values[largest] = tmp;
                cur = largest;
            } else {
                cur = -1; // sifted as far down as it needs to go
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        if (done) {
            PlotColor(70, 170, 90);   // fully sorted
        } else if (idx == cur) {
            PlotColor(220, 60, 60);   // being sifted down right now
        } else if (settled[idx]) {
            PlotColor(70, 170, 90);   // extracted into final position
        } else {
            PlotColor(30, 100, 200);  // part of the heap, not yet extracted
        }

        int height = values[idx] * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

cur hält den Knoten, der gerade versickert, oder -1, wenn nichts versickert und die nächste Aufgabe ausgewählt werden muss: In der Aufbauphase bedeutet das, an buildIndex (rückwärts gezählt ab der Mitte des Arrays — Blätter brauchen kein Versickern, da sie keine Kinder haben) ein Versickern zu starten; in der Extraktionsphase bedeutet das, die Wurzel mit values[extractEnd] zu tauschen, diese Position als final zu markieren, heapSize zu verkleinern und ein Versickern an der Wurzel zu starten. Ein Aufruf von frame() führt einen Vergleichs- und gegebenenfalls Tausch-Schritt des jeweils aktiven Versickerns aus.

• blau — Teil des Heaps, noch nicht extrahiert
• rot — der Knoten, der gerade versickert
• grün — extrahiert, an seiner finalen sortierten Position

Schritt für Schritt durchgerechnet

[1, 8, 4] versickern (Index 0 enthält 1, seine Kinder enthalten 8 und 4), um die Heap-Invariante an der Wurzel wiederherzustellen:

Nach dem Tausch ist das Array [8, 1, 4], und die Max-Heap-Invariante gilt: 8 ≥ 1 und 8 ≥ 4. Index 1 hat hier keine Kinder, also stoppt das Versickern. Einen vollständigen Heap aufzubauen wiederholt das für jeden Nicht-Blatt-Knoten, beginnend bei den untersten, sodass bereits alles darunter ein gültiger (kleinerer) Heap ist, wenn ein Versickern einen höheren Knoten erreicht.

Warum die In-place-Garantie wichtig ist

Heapsort erreicht dieselbe Worst-Case-Grenze von O(n log n) wie Merge Sort — beide leisten log n Ebenen Arbeit, O(n) pro Ebene, bedingungslos — aber mit O(1) zusätzlichem Speicher statt eines zweiten, eingabegroßen Arrays. Das macht Heapsort genau dort attraktiv, wo Merge Sorts zusätzliche Allokation ein Problem ist: speicherbeschränkte Systeme, oder überall, wo eine In-place-Worst-Case-Garantie gebraucht wird, ohne Quicksorts eingabeabhängiges Risiko.

Der Kompromiss ist das Cache-Verhalten: Heapsorts Zugriffe über 2i + 1 / 2i + 2 springen im Array herum statt es sequenziell zu durchlaufen, wie es Merge Sorts lineare Merges und Quicksorts lineare Partitionierungs-Scans tun. In der Praxis macht das Heapsort bei typischen Eingaben eher langsamer als Quicksort oder Merge Sort, trotz gleichwertiger oder besserer asymptotischer Garantien — genau deshalb verwendet Introsort standardmäßig Quicksort und fällt nur als Grenze für den Worst Case auf Heapsort zurück, statt es direkt zu verwenden.

Fazit

Heapsort fasst Sortieren als eine Folge von Priority-Queue-Operationen auf: eine Struktur aufbauen, die ihr Maximum immer an der Wurzel zeigt, dann dieses Maximum entfernen, ein Element nach dem anderen, günstig genug, dass n Extraktionen aus einem schrumpfenden Heap trotzdem nur O(n log n) ergeben. Es ist eine gute Erinnerung daran, dass "eine Liste sortieren" und "wiederholt das größte verbleibende Element finden" dasselbe Problem aus zwei Blickwinkeln sind.