Baum und Heap
Ebene Wurzel.
Ebene
Söhne von Ebene
.
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
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. ,
linker Sohn von Knoten erhält die Nr.
rechter Sohn von Knoten erhält die Nr.
Im Array
int[] a = new int [n];steht in a[i] der Schlüssel von Knoten
Aufwand für die Konstruktion eines Heaps
Sei die Höhe eines Heaps.
Sei
die Anzahl seiner Elemente.
Z.B. Ein Heap mit
Ebenen kann maximal
Knoten haben.
Ebene | Sickertiefe | Anzahl der Knoten dieser Ebene |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Anzahl der Schritte, beginnend bei vorletzter Ebene (), endend bei Ebene 0:
Aufwand
, denn:
Aufwand für einmaliges Minimumentfernen:
Gesamtaufwand:
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 ![]() |
![]() |
heapempty | testet, ob Heap leer ist |
Idee für Einfügen:
Füge neues Blatt mit Schlüssel an, und lasse
hochsickern.
Aufwand: