Hilfe Hauptseite Vorherige Naechste
Logo
Navigationsleiste
1. Der Binomial Heap Algorithmus

5. Implementierung der Binomial Heap Datenstruktur


Einleitung In den Kapiteln 3 und 4 wurde der Binomial Heap zur Erläuterung der Datenstruktur und der Funktionen recht abstrakt dargestellt. Aber bei der Implementierung des Binomial Heap Algorithmus dürfte diese abstrakte Form nicht effizient genug implementiert werden können. Denn eine direkte Implementierung dieser Datenstruktur verlangt es, daß Bäume mit unbeschränkter Ordnung programmtechnisch realisiert werden, da die Wurzel eines Binomialbaums BN N Söhne hat. Deshalb müßte die Menge der Söhne eines Knotens durch eine verkettete Liste beliebiger Länge dargestellt werden. Dies ist aber für zeitkritische Anwendungen, die mit dem Binomial Heap Algorithmus ja realisiert werden sollen (z.B. Prozess-Queue eines Betriebssystems), nicht akzeptabel. Deshalb wird in der Praxis die nun folgende Implementierungsform benutzt.

Die Implementierung der Datenstruktur Um eine effiziente Implementierung der Binomial Heap Datenstruktur zu erreichen, werden die Binomialbäume als Binärbäume dargestellt. Jedes im Binomialbaum gespeicherte Element hat dabei neben dem eigentlichen Datenfeld zwei Zeiger:
  1. Den Zeiger sibling , der auf seinen rechten Nachbarn zeigt.
  2. Den Zeiger child , der auf den linken Sohn zeigt.
Hat ein Knoten nun keinen rechten Nachbarn, kann dieser Zeiger auf den Vater des Knotens zurückweisen. Mit dieser Form der Repräsentation eines Binomialbaums durch einen Binärbaum ist eine effiziente Implementierung des Binomial Heap Algorithmus möglich. Folgende Grafik zeigt einen so aufgebauten Knoten:



Cormen erweitert in [Cormen90] diese Datenstruktur noch um weitere Felder:
  1. Den Zeiger P , der auf den Vater des Knotens zeigt. Dadurch braucht nicht der Knoten sibling als Zeiger auf den Vaterknoten "mißbraucht" zu werden, und es ist von jedem Knoten aus möglich, zum Vaterknoten zu gelangen. Ist P = NIL, dann muß dieser Knoten eine Wurzel sein.
  2. Die Variable Degree , in der die Anzahl der Söhne gespeichert ist. Durch diesen Wert können bei der Implementierung der Funktionen schnell die Bäume mit der gleichen Anzahl von gespeicherten Elementen ermittelt werden (sinnvoll z.B. bei der Verschmelzen - Funktion).
Mit den obigen Erweiterungen hat ein Knoten im Binomial Heap folgenden Aufbau:



Ein Beispiel Nun soll an einem Beispiel verdeutlicht werden, wie eine abstrakte Darstellung in der implementierungsnahen Darstellung aussieht. Folgende Grafik zeigt einen Binomial Heap, wie er aus den Kapiteln 3 und 4 bekannt ist:


Dieser Heap wird in der auf dieser Seite kennengelernten Repräsentation wie folgt gespeichert:


In der implementierungsnahen Darstellung werden die Binomialbäume also von links nach rechts miteinander verbunden. Dies liegt daran, daß der sibling-Zeiger, der zur Verbindung der Wurzeln benutzt wird, immer auf den rechten Nachbarn zeigt. Die einzelnen Binomialbäume sind aber identisch abgespeichert.

Auf dieser Seite wurde die konkrete Implementierung der Binomial Heap Datenstruktur vorgestellt. Wie sehen nun die Implementierungen der in Kapitel 4 behandelten Funktionen auf dieser Datenstruktur aus? Zu diesem Thema wird in Kapitel 6 eine Zuordnungsübung angeboten.

1. Der Binomial Heap Algorithmus
Seitenanfang Vorherige Naechste
Navigationsleiste