Heapsort

Baum und Heap

Def.:

Ein binärer Baum ist entweder leer oder besteht aus einem Knoten, dem zwei binäre Bäume zugeordnet sind. Dieser heißt dann Vater des linken bzw. rechten Teilbaums. Ein Knoten ohne Vater heißt Wurzel. Die Knoten, die x zum Vater haben, sind seine Söhne. Knoten ohne Söhne heißen Blätter. Ebene 0 = Wurzel. Ebene i + 1 = Söhne von Ebene i .

Def.:

Ein Heap ist ein binärer Baum mit n + 1 Ebenen, in dem die Ebenen 0,1,...,n - 1 vollständig besetzt sind; Ebene n ist von links beginnend bis zum so genannten letzten Knoten vollständig besetzt. Die Knoten enthalten Schlüssel. Der Schlüssel eines Knotens ist kleiner oder gleich den Schlüsseln seiner Söhne.

Offenbar steht der kleinste Schlüssel eines Heaps in der Wurzel.

Idee für Heapsort:

Verwendet wird ein Heap als Datenstruktur, die das Entfernen des Minimums unterstützt.

Gegeben seien die Schlüssel a₁,...,a_n .

Baue einen Heap auf mit den Schlüsseln a₁,...,a_n .
do {
     entferne Wurzel; // = Minimum
     reorganisiere Heap;
} while (Heap ist nicht leer);

Idee für Wurzelentfernen:

Entferne ``letzten'' Knoten im Heap und schreibe seinen Schlüssel in die Wurzel.

Vertausche so lange Knoten mit ``kleinerem'' Sohn, bis Heapbeziehung eintritt.

Problem:

Wie implementiert man einen Heap?

Lösung:

Die Knoten werden wie folgt nummeriert:
Wurzel erhält Nr. 0,
linker Sohn von Knoten i erhält die Nr. (2 · i + 1)
rechter Sohn von Knoten i erhält die Nr. (2 · i + 2)

Im Array

double[] a = new double [n];

steht in a[i] der Schlüssel von Knoten i .

Vorteil:

Die Vater/Sohn-Beziehung ist allein aus dem Knotenindex zu berechnen.
2i + 1 bzw. 2i + 2 heißen die Söhne von i
(i - 1)/2 heißt der Vater von i .

public static int vater(int i) { // liefert den Index des Vaters von i
   return (i-1)/2;               // (Spezialfall: vater[0] == 0)
}

Source: HeapSort.java     JavaDoc: HeapSort.html    

Aufwand für die Konstruktion eines Heaps

Sei h die Höhe eines Heaps. Sei n - 1 = 2^h - 1 die Anzahl der Elemente, z.B. 15 = 2⁴ - 1 .

Ebene Sickertiefe Anzahl

h - 1 1

h - 2 2

h - 3 3

0 h

Anzahl der Schritte:

Aufwand O(n) , denn: + + +...< 2

Aufwand für einmaliges Minimumentfernen: O(log n)

Gesamtaufwand: O(n) + O(n · logn) = O(n · log n)

     für best, average und worst case.

Weitere Einsatzmöglichkeit des Heaps

Verwende eine dynamisch sich ändernde Menge von Schlüsseln mit den Operationen

initheap legt leeren Heap an

get_min liefert das momentan Kleinste

del_min entfernt das momentan Kleinste

insert(x) fügt x hinzu

heapempty testet, ob Heap leer ist

Idee für Einfügen: (schlecht: von oben nach unten)
besser: Füge neues Blatt mit Schlüssel x an, und lasse x hochsickern.

i = neuer Index;
while (a[i] < a[vater(i)]){ 
   tausche a[i] mit a[vater(i)];
   i = vater(i);
}

Aufwand O(log n)

Untere Schranke für Sortieren durch Vergleichen

Entscheidungsbaum zur Sortierung von 3 Elementen:
gegeben A,B,C

Der Entscheidungsbaum zur Sortierung von n Elementen hat n ! Blätter.

Ein binärer Baum mit n! Blättern hat mindestens die Höhe · log n .

Jeder Sortieralgorithmus, der auf Vergleichen beruht, hat als Laufzeit mindestens
O(n · log n) . Dies ist eine untere Schranke.