Zur MathePrisma-Startseite
Zur Modul-Startseite  


Binäre Suchbäume (Heap 2)
 
 
 

 
 Für die Datenstruktur Heap gibt es die folgenden zwei Operationen:
 
Operationen
 
  • einfügen( s ) fügt einen neuen Datensatz mit Schlüssel s in den Heap ein.
  • Maximum entfernen entfernt den Datensatz mit maximalem Schlüssel aus dem Heap und liefert ihn zurück.
 

 
 Im Gegensatz zu binären Suchbäumen kann man nicht nach beliebigen Datensätzen suchen oder solche löschen.
 

 
 Wie wird eingefügt?
 
Heap einfügen

 
 Algorithmus zum Einfügen von Schlüssel s
  • Platziere s vorläufig im nächsten freien Knoten k am Ende des Heap.
  • Solange s größer ist als der Schlüssel des Vaters, vertausche k mit seinem Vater (sift up).
 


Füge auch große Schlüssel ein!
 

 
 Und nun zum Entfernen des Maximums. Wie war das noch einmal mit dem Maximum beim Heap?
 
Das Maximum muss beim Heap
 
durch einen Suchalgorithmus gesucht werden.
immer in der Wurzel liegen.
immer die größte Tiefe haben.
 
 
 

 
 Damit ist klar, wo das Maximum im Heap liegt. Wie stellt man die Heap-Struktur wieder her, wenn man das Maximum entfernt hat?
 
Maximum entfernen
 
 Algorithmus zum Maximum entfernen
  • Speichere den Schlüssel in der Wurzel des Heaps als Rückgabewert.
  • Ersetze die Wurzel durch den letzten Knoten k des Heaps.
  • Solange k mindestens einen Sohn mit größerem Schlüssel besitzt, vertausche k mit dem Sohn, dessen Schlüssel am größten ist (sift down).
 

 
 In dem folgenden Experiment kannst du dir Heaps mit unterschiedlich vielen Knoten ansehen, weitere Knoten einfügen und löschen.
 
 

 
 Warum ist der Heap eine wichtige Datenstruktur?

Betrachte dazu den Aufwand für 'einfügen' und 'Maximum entfernen'. Es werden nie mehr als h Einzelschritte benötigt! Der Aufwand wird also durch die Höhe h des Binärbaumes bestimmt. Als dichter Binärbaum hat der Heap minimale Höhe.
 
Wie groß ist die Höhe h eines Heaps mit 7 Knoten?
h =  
Und mit 17 Knoten? h =  
Und mit n Knoten, wobei n zischen den folgenden beiden Zahlen liegt?


h =  
 
 
 



 

 Die letzte Antwort besagt: Die Höhe h eines Heaps mit n Knoten ist die größte ganze Zahl Man schreibt:



Damit folgt die Aussage:

 
Aufwand
 
 Einfügen bzw. Maximum entfernen bei einem Heap mit n Knoten erfordert höchstens


Einzelschritte.

 
Seite 11/11