Binäre Suchbäume | MathePrisma

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?

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.

$2^N \leq n \leq 2^{N+1}-1$

Die letzte Antwort besagt: Die Höhe h eines Heaps mit n Knoten ist die größte ganze Zahl $\leq \log_2(n)$ Man schreibt:

$h=\lfloor\log_2(n)\rfloor$

Damit folgt die Aussage:

Aufwand

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

$\lfloor\log_2(n)\rfloor$

Einzelschritte.