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

3.2 Die Binomial Heap Datenstruktur


Einleitung Wie in Kapitel 3.1 beschrieben, kann ein einzelner Binomialbaum nur 2n Elemente speichern. Um beliebig viele Elemente im Priority Queue speichern zu können, wird deshalb der Binomial Heap als Datenstruktur verwendet.

Definition des Binomial Heaps Der Binomial Heap ist ein Wald von Binomialbäumen. Er setzt sich also aus eine variablen Zahl von Binomialbäumen zusammen. Die einzelnen Binomialbäume müssen dabei ebenfalls heapgeordnet sein. Doch welche Binomialbäume werden für die Speicherung von N Elementen benötigt?

Das duale Zahlensystem Angenommen, in einem Binomial Heap sollen N Elemente gespeichert werden. Wenn man die Zahl N als Dualzahl dn-1dn-2...d0 darstellt, so muß für jede Stelle i, an der diese Dualzahl eine 1 hat, ein Binomialbaum Bi im Binomial Heap vorhanden sein. Sollen z.B. 11 Elemente in einem Binomial Heap gespeichert werden, so ist die duale Darstellung von 11 = 10112. Daraus folgt, daß in einem Binomial Heap die Binomialbäume B3, B1 und B0 mit jeweils acht, zwei und einem Element benötigt werden, um die 11 Elemente speichern zu können. Hier eine Grafik von einem Binomial Heap, in dem 11 beliebige Elemente gespeichert sind:



Der Binomial Heap Diese Datenstruktur zur Speicherung von N Elementen ist der Binomial Heap. Um den Binomial Heap zur Verwaltung eines Priority Queues verwendet zu können, müssen die für einen Priority Queue benötigten Funktionen "Initialisieren", "Minimum Suchen", "Element Einfügen", "Verschmelzen" und "Minimum Entfernen" auf dieser Datenstruktur definiert werden. Die Behandlung dieser Funktionen soll nun in Kapitel 4 durchgeführt werden.

1. Der Binomial Heap Algorithmus / 3. Der Binomial Heap
Seitenanfang Vorherige Naechste
Navigationsleiste