Algorithmen und Datenstrukturen in C/ Heapsort
Heapsort ist ein Sortieralgorithmus, der auf der Verwendung eines binären Heaps basiert. Eine solide Kenntnis dieser Datenstruktur ist für die weitere Lektüre dieses Kapitels erforderlich. Für dieses Kapitel relevante Informationen finden sich im Kapitel Heaps.
Problemstellung
[Bearbeiten]Gesucht ist ein Algorithmus, der die folgenden Forderungen erfüllt.
Eingabe:
- eine Folge von n Schlüsseln k1, k2, ..., kn
Ausgabe:
- eine Folge bestehend aus den Schlüsseln k1, k2, ..., kn in sortierter Reihenfolge
Idee
[Bearbeiten]Die Wurzel eines Min-Heap enthält zu jedem Zeitpunkt den kleinsten aller in ihm abgelegten Schlüssel.
Werden zunächst alle zu sortierenden Schlüssel in einen Min-Heap H eingefügt, so findet sich der kleinste Schlüssel an der Wurzel. Werden die in der Wurzel gespeicherten Schlüssel nun sukzessive entfernt, so werden die in H abgelegten Schlüssel in sortierter Reihenfolge zurückgeliefert.
Algorithmus
[Bearbeiten]Der Algorithmus arbeitet in zwei Phasen.
- In der ersten Phase werden die zu sortierenden Schlüssel ki schrittweise in einen Min-Heap H eingefügt
- In der zweiten Phase wird schrittweise der in der Wurzel von h gespeicherte Schlüssel entfernt und der sortierten Folge hinzugefügt
In Phase 1 werden n Schlüssel hinzugefügt. Die insert() Operation hat eine worst-case Laufzeit von O(log n). Die worst-case Laufzeit für des Einfügen aller Schlüssel beträgt somit O(n log n).
In Phase 2 wird der in der Wurzel von H gespeicherte Schlüssel genau n Mal entfernt. Die extract() Operation hat eine worst-case Laufzeit von O(log n). Die worst-case Laufzeit für Phase 2 beträgt somit ebenfalls O(n log n).
In Summe hat der Algorithmus somit eine worst-case Laufzeit von O(n log n).
Naive Implementierung
[Bearbeiten]Steht für die Umsetzung des vorgestellten Algorithmus bereits eine Min-Heap Implementierung wie die aus dem Kapitel Heaps bereit, so kann das Sortieren der in einem Array keys der Länge n_keys gespeicherten Schlüssel direkt wie folgt in C-Code umgesetzt werden.
void naive_heapsort(int keys[], int n_keys) {
Heap h;
int *storage = malloc(n_keys * sizeof(int));
heap_init(&h, storage);
for (int i=0; i < n_keys; ++i) { // <1>
min_heap_insert(&h, keys[i]);
}
for (int i=0; i < n_keys; ++i) { // <2>
keys[i] = min_heap_extract(&h);
}
free(storage);
}
Ein Nachteil der naiven Implementierung besteht darin, dass für die Speicherung der Schlüssel im Heap h zusätzlicher Speicherplatz benötigt wird.
Im folgenden Abschnitt wird es darum gehen diese Schwachstelle zu beheben.
In-place Implementierung
[Bearbeiten]Wirft man einen genauen Blick auf den Ablauf der einzelnen Arbeitsschritte des Algorithmus, so fällt auf, dass der bereits für die zu sortierenden Schlüssel bereitgestellte Speicherplatz zugleich wie folgt für die Speicherung der im Heap abgelegten Schlüssel verwendet werden kann.
- In Phase 1 kann der Teil des Arrays, dessen Schlüssel bereits eingefügt wurden, für die Speicherung der Schlüssel des Heaps verwendet werden.
- In Phase 2 kann der Teil des Arrays, der nach dem Entfernen des in der Wurzel gespeicherten Schlüssels nicht mehr für die Schlüssel des Heaps benötigt wird, für die Aufnahme der Schlüssel der sortierten Folge verwendet werden.
Das Array wird dabei in umgekehrter Richtung gefüllt. Um die Elemente in aufsteigender Reihenfolge zu sortieren, muss anstelle eines Min-Heaps daher ein Max-Heap verwendet werden. Mit der Max-Heap Implementierung aus dem Kapitels Heaps kann die in-place Variante direkt wie folgt in C-Code umgesetzt werden.
void heapsort(int keys[], int n_keys) {
Heap h;
heap_init(&h, keys);
for (int i=0; i < n_keys; ++i) {
max_heap_insert(&h, keys[i]);
}
for (int i=0; i < n_keys; ++i) {
keys[n_keys - i -1] = max_heap_extract(&h);
}
}
Vereinfachung
[Bearbeiten]Für die Umsetzung des Heapsort-Algorithmus werden lediglich die Operationen insert() und extract() eines Max-Heap verwendet.
Steht keine Max-Heap Implementierung zur Verfügung, so besteht keine Notwendigkeit das volle Spektrum aller von einem Max-Heap zur Verfügung gestellten Operationen in C-Code umzusetzen.
Bei der Implementierung ist es an mehreren Stellen nötig, die Schlüssel zweier Knoten miteinander zu vertauschen. In der Praxis wird dieser Schritt aus Effizienzgründen in der Regel direkt an der jeweiligen Stelle implementiert werden.
Um den Code möglichst übersichtlich zu halten, wird für das Vertauschen der Schlüssel zweier Knoten m und n hier die folgende Hilfsfunktion verwendet werden.
void swap(int* keys, int n, int m) {
int tmp = keys[n];
keys[n] = keys[m];
keys[m] = tmp;
}
Mit der Hilfsfunktion swap() kann der Heapsort-Algorithmus wie folgt in C-Code umgesetzt werden.
void heapsort(int *keys, int n_keys) {
keys -= 1;
/* PHASE 1: insert keys */
for (int last=1; last <= n_keys; ++last) {
/* bubble up */
int n = last;
while(n > 1) {
int parent = n/2;
if (keys[parent] > keys[n])
break;
swap(keys, parent, n);
n = parent;
}
}
/* PHASE 2: extract */
for (int last=n_keys-1; last >= 1; --last) {
swap(keys, 1, last+1); /* i.e: keys[last+1] = delete(1) */
/* sift down */
int n = 1;
while (1) {
int max = n;
int left = n * 2;
int right = left + 1;
if (left <= last && keys[left] > keys[max])
max = left;
if (right <= last && keys[right] > keys[max])
max = right;
if (n == max)
break;
swap(keys, max, n);
n = max;
}
}
}
Quellcode
[Bearbeiten]Zwecks besserer Übersicht hier der vollständige Quellcode am Stück.
#include <stdio.h>
void swap(int* keys, int n, int m) {
int tmp = keys[n];
keys[n] = keys[m];
keys[m] = tmp;
}
void heapsort(int *keys, int n_keys) {
keys -= 1;
/* PHASE 1: insert keys */
for (int last=1; last <= n_keys; ++last) {
/* bubble up */
int n = last;
while(n > 1) {
int parent = n/2;
if (keys[parent] > keys[n])
break;
swap(keys, parent, n);
n = parent;
}
}
/* PHASE 2: extract */
for (int last=n_keys-1; last >= 1; --last) {
swap(keys, 1, last+1); /* i.e: keys[last+1] = delete(1) */
/* sift down */
int n = 1;
while (1) {
int max = n;
int left = n * 2;
int right = left + 1;
if (left <= last && keys[left] > keys[max])
max = left;
if (right <= last && keys[right] > keys[max])
max = right;
if (n == max)
break;
swap(keys, max, n);
n = max;
}
}
}
/* MAIN --------------------------------------------------------------- */
int main(int argc, char* argv[]) {
int keys[] = { 3, 8, 2, 7, 14, 1, 13, 6, 4, 10, 12, 15, 23 };
int n_keys = sizeof(keys) / sizeof(int);
heapsort(keys, n_keys);
for (int i=0; i < n_keys; ++i)
printf("%d ", keys[i]);
printf("\n");
return 0;
}
Für die examplarisch in main() hinterlegte Folge 3, 8, 2, 7, 14, 1, 13, 6, 4, 10, 12, 15, 23 liefert der implementierte Algorithmus die folgende Ausgabe.
1 2 3 4 6 7 8 10 12 13 14 15 23