Baum und Heap
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 a1,...,an .
Baue einen Heap auf mit den Schlüsseln
a1,...,an .
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.
Im Array
double[] a = new double [n];steht in a[i] der Schlüssel von Knoten 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 = 2h - 1 die Anzahl der Elemente, z.B. 15 = 24 - 1 .
Ebene | Sickertiefe | Anzahl |
h - 1 | 1 | |
h - 2 | 2 | |
h - 3 | 3 | |
0 | h | =1 |
Anzahl der Schritte:
c · i · = c · n · |
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.
n! n · (n - 1) · (n - 2) · ... · |
log n! | log · log (log n - 1) | ||
= | · logn - = · logn + · logn - | ||
· lognn 4 |