Fun with binary heap trees

Binary Heap Trees

• Definition
• Anwendungen
• Funktionen auf Binary Heap Trees
• Beispiele für die sechs join Varianten

Definition

Bei Binary Heap Trees handelt es sich um eine besondere Art der Binärbäume. Sie lassen sich durch folgende Datenstruktur repräsentieren:

Die Daten werden hier nicht am Ende eines Weges durch den Baum in einem Blatt gespeichert sondern direkt in den einzelnen Knoten des Baumes. Dabei gilt, dass die Werte der Kind-Knoten eines Baumes immer größer oder gleich dem Wurzelelement sein müssen. Dies setzt sich durch die rekursive Definition der Datenstruktur bis in die Blätter fort. Dies hat den Vorteil, dass sich das kleinste Element des Baumes immer in der Wurzel befindet und somit extrem leicht zu ermitteln ist.

Zwischen dem linken und dem rechten Ast eines Baumes ist keine Ordnungsrelation definiert. Hier ist man, wenn man von Performance-Gesichtspunkten absieht frei ein der Auswahl einer Einfüge-Strategie. Aus diesem Grunde müssen Binary Heap Trees auch keine "Balanced Trees" sein. Es theoretisch denkbar, einen Binary Heap Tree als sortierte lineare Liste zu implementieren.

Anwendungen

Binary Heap Trees eignen sich dadurch, dass sich das kleines Element immer in der Wurzel befindet für Warteschlangen mit Prioritäten. Bei solchen Warteschlangen hat immer das Element mit der kleinsten Prioritätszahl die höchste Priorität und wird zuerst verarbeitet. Da sich dieses Element bereits in der Wurzel befindet, ist es sehr einfach zu ermitteln.

Eine andere Anwendung ist allgemein das Sortieren von Elementen einer Liste. Binary Heap Trees können, wenn sie richtig implementiert wurden, sehr effizient beim Sortieren arbeiten. Die Zeitkomplexität ist hier O(log n).

Funktionen auf Binary Heap Trees

Für die Verwendunge von Binary Heap Trees müssen wir folgende Funktionen zur Verfügung stellen. Eine für den Test auf Leere, da wir auch leere Bäume erzeugen können, eine zur Ermittlung des kleinsten Elements, zum Löschen des kleinsten Elements, zum Einfügen eines neuen Elementes in einen vorhandenen Baum und schliesslich eine zum Zusammenführen von zwei Bäumen.

Die ersten beiden Funktionen sind sehr einfach zu implementieren. Sie laufen in konstanter Zeit:

Die beiden Funktionen deleteMin und insert können auf die Funktion merge abgebildet werden, da sie jeweils nur Sonderfäll dieser sind. Damit besitzen diese die gleiche Laufzeitkomplexität wie merge.

Bleibt noch die merge Funktion zu implementieren. Für die Fälle, dass ein Baum mit einem leeren Baum zusammengeführt wird, ist der Fall recht einfach: Der Baum bleibt, wie er ist. In allen anderen Fällen muss der Baum mit dem kleineren Wurzelelement ermittelt werden und mit dem anderen Baum verschmolzen werden. Dazu wird die Funktioen join eingeführt.

In der join Funktion schliesslich müssen die drei Bäume, die nach dem Extrahieren des neuen Root-Elementes übrig bleiben auf die beiden Äste der Wurzel verteilt werden. Dazu müssen zwei dieser Bäume wieder zusammengefasst werden.

Es gibt insgesamt sechs verschiedene Arten, diese drei Bäume zusammenzuführen. Aber welche ist die sinnvollste?

Beispiele für die sechs join Varianten

Die folgenden Bäume entstanden jeweils durch das Einfügen der folgenden Zahlenfolge: 5, 2, 1, 6, 3, 4.