Baum und Heap
Ebene 0 = Wurzel. Ebene i + 1 = Söhne von Ebene i.
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.
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 . 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.
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 &ge#geq;4 |