Ein Binärbaum als Priorityqueue

Wozu eigentlich?

Gelegentlich muss man eine sich ändernde Menge in der Reihenfolge ihrer jeweils kleinsten Elemente abarbeiten (z.B. bei der A* Wegesuche). Dazu dient eine Priorityqueue. Sie ist gerne als Binärer Minimum Heap implementiert. Das geschieht entweder explizit über Knoten mit Verweisen auf linken und rechten Teilbaum oder in Form eines Arrays, bei dem die Art der Indexberechnung der Kinder- bzw. Elternknoten einen direkten Verweis überflüssig macht.

Was ist ein binärer Heap?

Ein binärer Heap ist eine über Schlüssel geordnete (Baum)Datenstruktur. In ihr sind alle Ebenen, bist auf die letzte, komplett gefüllt. Die letzte Ebene wird dicht von links nach rechts gefüllt. Die Knoten haben maximal zwei Kinder. Das Beispielprogramm ist als Min Heap realisiert, bei dem jeder Kindknoten einen größeren Schüssel als sein Elternknoten hat. Das kleinste Element findet sich immer an der Wurzel. Durch hinzufügen und entfernen von Knoten kann die Ordnung gestört werden und muss zwingend wieder hergestellt werden.

Wie sieht ein Knoten aus?

Die Knoten müssen Instanzen einer Klasse sein. Die Klasse muss das Interface IComparable implementieren, weil sonst eine Sortierung im Baum unmöglich ist. Um eine Baumtraversierung auszugeben, sollte ToString entsprechend überschrieben sein.

Quelltext ein-/ausblenden

Vom Array zum Binärbaum.

Das ist einfach und geht schnell. Das Array wird als Binärbaum betrachtet. Die Arrayindices verweisen auf die Knoten. Unterschieden werden 0 und 1 basierte Arrays. Bei 1 basierten Arrays hat der Knoten Ki das linke Kind K2i und das rechte Kind K2i + 1. Der Elternknotenindex von Ki ist abgerundet i/2. Das 0te Element wird als Zwischenspeicher für Verwaltungsaufgaben verwendet.
1 basierte Arrays sind in diesem Fall wegen der Indexberechnung einfacher. Die Art der Indexberechnung enthält implizit die Beziehung von Eltern- und Kindknoten. Die Indices oder Verweise brauchen daher nicht extra gespeichert werden. Hier wird ein 1 basiertes Array genutzt.

Der Zugriff auf den Baum.

Die MinBinaryHeapArray Klasse bietet Zugriffe über:

  • 2 Konstruktoren zum Erzeugen eines leeren Baumes oder eines Baumes, der über ein (dichtes Daten)Array initialisiert wird. Im Baum werden Knoten Klassen, die IComparable implementieren, verwaltet. Die Knoten Klasse sollten wegen der Traversierung ToString überschreiben.
  • Add Funktion zum Hinzufügen einzelner Knoten und ggf. zum Vergrößern des Arrays.
  • Clear Funktion zum Löschen aller Elemente
  • ExtractMin Funktion zur Entnahme des kleinsten Elementes.
  • GetMin Funktion zum Lesen des kleinsten Elementes.
  • 4 Funktionen zum Traversieren des Baumes.

Die wichtigsten internen Funktionen sind Heapify und Decrease. Beide dienen dem Zweck, die Heap - Bedingung (Eltern sind kleiner als Kinder) zu sichern/herzustellen. Heapify betrachtet dazu die Kindknoten eines Knotens. Decrease untersucht den Elternknoten eines Knotens. Beide tauschen Knoten, um die Heapbedingung herzustellen.

Alle Knoten eines Binärbaumes einmal besuchen

Wenn man alle Knoten eines Binärbaumes besuchen will, kommen vier Möglichkeiten in Betracht.

  1. levelorder Durchlauf: Im Array über den Index iterieren. Besucht in Ebenenfolge alle Knoten.
  2. inorder Durchlauf (L K R )
    • inorder Durchlauf: für den linken Teilbaum des Knotens k
    • Knoten k selbst besuchen
    • inorder Durchlauf für den rechten Teilbaum des Knotens k
  3. preorder Durchlauf: (K L R)
    • Knoten k selbst besuchen
    • preorder Durchlauf für den linken Teilbaum des Knotens k
    • preorder Durchlauf für den rechten Teilbaum des Knotens k
  4. postorder Durchlauf: (L R K )
    • postorder Durchlauf für den linken Teilbaum des Knotens k
    • postorder Durchlauf für den rechten Teilbaum des Knotens k
    • Knoten k selbst besuchen

Quelltext ein-/ausblenden

Kommentar(e)

Kommentarformular ein-/ausblenden