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 $h$ Ebenen, in dem die Ebenen $0,1,\ldots , h-2$ vollständig besetzt sind; die letzte Ebene $h-1$ 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_{0},\ldots ,a_{n-1}$ im Array a.

Baue einen Heap mit den Werten aus a;
for (i=0; i<n; i++) {
  liefere Minimum aus der Wurzel;
  entferne Wurzel;
  reorganisiere Heap;
}

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.

Idee für Implementation: Die Knoten werden wie folgt nummeriert:
Wurzel erhält Nr. $0$,
linker Sohn von Knoten $i$ erhält die Nr. $(2\cdot i + 1)$
rechter Sohn von Knoten $i$ erhält die Nr. $(2\cdot i+2)$

Im Array

int[] a = new int [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$.

Source: HeapSort.java     JavaDoc: HeapSort.html    

Aufwand für die Konstruktion eines Heaps

Sei $h$ die Höhe eines Heaps. Sei $n \leq 2^{h}-1$ die Anzahl seiner Elemente. Z.B. Ein Heap mit $h=4$ Ebenen kann maximal $n = 2^{4}-1 = 15$ Knoten haben.

Ebene	Sickertiefe	Anzahl der Knoten dieser Ebene
$0$	$h$	$1$
$\vdots$	$\vdots$	$\vdots$
$h-3$	$3$	$\frac{n}{8}$
$h-2$	$2$	$\frac{n}{4}$
$h-1$	$1$	$\frac{n}{2}$

Anzahl der Schritte, beginnend bei vorletzter Ebene ($h-2$), endend bei Ebene 0:

$$\begin{eqnarray*} \sum_{i=2}^{h}c\cdot i\cdot \frac{n}{2^i}=c \cdot n\cdot \sum_{i=2}^{h}\frac{i}{2^{i}} \end{eqnarray*}$$

$\Rightarrow$ Aufwand $O(n)$, denn: $\frac{2}{4}+\frac{3}{8} +\frac{4}{16}+\ldots ~~< 1.5$

Aufwand für einmaliges Minimumentfernen: $O( \log n)$
Gesamtaufwand: $O(n)+O(n\cdot \log n)=O(n\cdot \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

$\bullet$	initheap	legt leeren Heap an
$\bullet$	get_min	liefert das momentan Kleinste
$\bullet$	del_min	entfernt das momentan Kleinste
$\bullet$	insert(x)	fügt $x$ hinzu
$\bullet$	heapempty	testet, ob Heap leer ist

Idee für Einfügen: Füge neues Blatt mit Schlüssel $x$ an, und lasse $x$ hochsickern.

Aufwand: $O( \log n)$