imported>Attraktor: Tote Weblinks repariert - beim 1. Link konnte ich das Java-Applet noch nicht testen

2022-07-29T22:51:21Z

Tote Weblinks repariert - beim 1. Link konnte ich das Java-Applet noch nicht testen

Neue Seite

In der [[Informatik]] ist ein '''Binomial-Heap''' eine [[Datenstruktur]], genauer ein [[Heap (Datenstruktur)|Heap]], der sich, ähnlich wie [[Binärer Heap|binäre Heaps]], als [[Vorrangwarteschlange]] einsetzen lässt. Das heißt, dass in beliebiger Reihenfolge [[Effizienz (Informatik)|effizient]] Elemente mit festgelegter Priorität in den Heap hineingelegt werden können und stets das Element mit höchster Priorität entnommen werden kann.

Im Unterschied zu binären Heaps können Binomial-Heaps auch effizient vereinigt werden.
Dies ermöglicht es beispielsweise, effizient in einem Mehrprozessor-[[Multitasking]]-[[System]] die Aufgaben eines überlasteten [[Prozessor]]s einem anderen zu übertragen.

Die Priorität der Elemente wird diesen durch [[Schlüssel (Informatik)|Schlüssel]] aufgeprägt.
Über der Menge der Schlüssel muss daher eine [[totale Ordnung]] bestehen, wie sie zum Beispiel die Kleiner-Gleich-Relation (≤) über den [[Ganze Zahl|ganzen Zahlen]] darstellt.

Binomial-Heaps wurden erstmals 1978 von [[Jean Vuillemin]] beschrieben. 1987 wurde von [[Michael L. Fredman]] und [[Robert Tarjan]] daraus eine neue Datenstruktur abgeleitet, die sogenannten [[Fibonacci-Heap]]s. Diese besitzen [[Amortisierte Laufzeitanalyse|amortisiert]] teilweise bessere Laufzeiten und finden unter anderem Anwendung im [[Algorithmus von Dijkstra]] und im [[Algorithmus von Prim]]. Ihre Worst-Case Laufzeit ist teilweise aber deutlich schlechter, weshalb sie sich nicht für [[Online-Algorithmus|Online-Algorithmen]] eignen.

== Operationen ==
Binomial-Heaps unterstützen effizient die Operationen

* ''insert'' – zum Einfügen eines Elementes,
* ''remove'' – zum Entfernen eines Elementes,
* ''extractMin'' – zur Rückgabe und zum Entfernen eines Elementes mit minimalem Schlüssel (=höchster Priorität),
* ''changeKey'' – zum Ändern des Schlüssels eines Elementes und
* ''merge'' – zum Verschmelzen zweier Heaps.

Alle Operationen lassen sich mit einer [[Asymptotische Laufzeit|Worst-Case-Laufzeit]] von ''O''(log ''n'') implementieren, wobei ''n'' die Zahl der aktuell im Heap befindlichen Elemente ist.

== Binomial-Bäume ==
[[Datei:Binomial-tree-3.svg|mini|Binomial-Baum der Ordnung 3]]

Binomial-Heaps bestehen aus einer Liste von Binomial-Bäumen verschiedener Ordnung. Binomial-Bäume und ihre Ordnung sind dabei wie folgt [[Rekursion|rekursiv]] definiert:

* Ein Binomial-Baum der Ordnung 0 besteht aus einem einzelnen [[Knoten (Graphentheorie)|Knoten]].
* Ein Binomial-Baum der Ordnung ''k'' besitzt eine [[Wurzel (Graphentheorie)|Wurzel]] mit [[Grad (Graphentheorie)|Grad]] ''k,'' deren Kinder genau die Ordnung ''k''−1, ''k''−2, ..., 0 (in dieser Reihenfolge) besitzen.

Ein Binomial-Baum der Ordnung ''k'' lässt sich also auch leicht aus zwei Binomial-Bäumen der Ordnung ''k''−1 erstellen, indem einer der beiden Bäume zum am weitesten links stehenden Kind des anderen gemacht wird. Aus dieser Konstruktion lässt sich leicht per [[Vollständige Induktion|vollständiger Induktion]] die Eigenschaft ableiten, dass ein Binomial-Baum der Ordnung ''k'' genau 2''k'' Knoten und die [[Höhe (Graphentheorie)|Höhe]] ''k'' besitzt.

== Struktur eines Binomial-Heaps ==
Ein Binomial-Heap speichert seine Elemente und die zugehörigen Schlüssel in den Knoten seiner Binomial-Bäume. Dabei erfüllt er folgende Eigenschaften:

* Jeder Binomial-Baum im Heap erfüllt die Heap-Bedingung, das heißt mit Ausnahme der Wurzel, die keinen [[Gewurzelter Baum#Weitere Begriffe|Elternknoten]] besitzt, gilt für jeden seiner Knoten, dass der zugehörige Schlüssel größer oder gleich dem Schlüssel seines Elternknotens ist.
* Für jede natürliche Zahl ''k'' existiert höchstens ein Binomial-Baum der Ordnung ''k''.

[[Datei:Binomial-heap-13.svg|miniatur|Beispiel eines Binomial-Heaps mit 13 Elementen. Die Schlüssel der Väter sind höchstens so groß wie die Schlüssel ihrer Kinder.]]

Die erste Eigenschaft gewährleistet, dass die Wurzel jedes Baumes ein Element mit kleinstem Schlüssel im Baum trägt. Zusammen mit der Eigenschaft, dass ein Binomial-Baum der Ordnung ''k'' genau 2''k'' Knoten besitzt, stellt die zweite Eigenschaft sicher, dass für einen Binomial-Heap mit ''n'' Elementen exakt festgelegt ist, wie viele Bäume der Heap besitzt und welche Ordnung diese besitzen.

Dies ist durch die [[Binärdarstellung]] von ''n'' festgelegt. Werden die Ziffern von rechts nach links mit 0 beginnend durchnummeriert, so existiert ein Baum der Ordnung ''k'' genau dann, wenn in der Binärdarstellung an der Stelle ''k'' eine 1 steht. Dies bedeutet auch, dass ein Heap mit ''n'' Elementen höchstens log2(''n''+1) Binomial-Bäume enthält. Ein Binomial-Heap mit 13=11012 Elementen besitzt beispielsweise genau einen Baum der Ordnung 3, einen Baum der Ordnung 2 und einen Baum der Ordnung 0.

Die Menge der Binomial-Bäume wird als (nach der Ordnung der Bäume) sortierte [[Liste (Datenstruktur)|Liste]] der Wurzeln dieser Bäume implementiert. Ein Binomial-Heap besitzt im Gegensatz zum Binär-Heap nicht eine einzige Wurzel, sondern mehrere. Diese werden als ''Wurzelliste'' bezeichnet. Dadurch erhöht sich die Laufzeit für das Finden des Minimums auf ''O''(log ''n''), da alle Elemente der Wurzelliste durchsucht werden müssen.

== Implementierung der Operationen ==

=== Verschmelzen zweier Heaps ''(merge)'' ===
[[Datei:Binomial heap merge1.svg|links|mini|Verschmelzen zweier Binomialbäume von Grad 2: Vergleiche die Wurzeln und füge dem Baum mit kleinerer Wurzel (grau) den anderen Baum (schwarz) als linken Teilbaum hinzu. Am Ende erhält man so den unteren Baum mit Grad 3.]]

Die zentrale Operation ist das Verschmelzen zweier Heaps ''(merge)'', da diese als [[Unterprogramm]] aller anderen Operationen verwendet wird. Die Operation erfolgt ähnlich der [[Dualsystem#Grundrechenarten im Dualsystem|bitweisen Addition]] von [[Dualzahl]]en. In diesem Fall entspricht dies der [[Addition]] der Anzahl der Elemente ''n''1 und ''n''2 der zu verschmelzenden Heaps.

Dazu werden simultan die Listen der beiden Heaps beginnend bei den Bäumen niedrigster Ordnung durchlaufen. In einer speziellen [[Variable (Programmierung)|Variablen]] wird – ähnlich der bitweisen Addition – ggf. ein Übertrag (in Form eines Baumes) festgehalten. Anfangs ist dieser Übertrag leer.

Sei nun ''x'' die höchste Binärstelle von <math>n_1+n_2</math> verschieden von 0, das heißt <math>x=\log_2(n_1+n_2+1)-1</math>. Zu jeder natürlichen Zahl ''k'' mit <math>0\leq k\leq x</math> wird nun in aufsteigender Reihenfolge die Anzahl der Bäume mit Ordnung ''k'' in beiden Heaps und in der Übertragsvariablen betrachtet. Ist diese

* 0, so passiert nichts.
* 1, so wird der entsprechende Baum in den neuen Heap übernommen und der Übertrag ggf. geleert.
* 2, so wird der Baum, dessen Schlüssel an der Wurzel größer ist, zum am weitesten links stehenden Kind des anderen Baumes gemacht und der so entstehende Baum der Ordnung ''k''+1 als Übertrag behalten.
* 3, so wird der Baum aus dem Übertrag in den neuen Heap übernommen und von den beiden Bäumen in den Heaps wird der Baum, dessen Schlüssel an der Wurzel größer ist zum am weitesten links stehenden Kind des anderen Baumes gemacht und der so entstehende Baum der Ordnung ''k''+1 als Übertrag behalten.

Jeder dieser Schritte lässt sich in konstanter Zeit durchführen. Da maximal <math>\log_2(n_1+n_2+1)</math> derartige Schritte getätigt werden, benötigt die Operation im [[Worst Case|schlimmsten Fall]] nur [[Logarithmus|logarithmisch]] viel Zeit.

=== Entfernen eines Elementes ''(remove)'' ===
[[Datei:Binomial-heap-split.svg|mini|Aufspalten eines Binomial-Baumes mittels ''split''. Dreiecke symbolisieren die neuen Teilbäume. Die Beschriftung der Knoten bezeichnet deren Ordnung vor beziehungsweise nach dem Aufspalten. Es gilt ''k''>''a1''>''a2''>...>''ai''=''x'', wobei ''i''+1 die Tiefe von Knoten ''X'' im Baum ist.]]

Neben ''merge'' ist das Entfernen eines Elementes ''(remove)'' die anspruchsvollste Operation. Sei ''X'' das zu entfernende Element, seine Ordnung ''x'' und ''T'' der Binomial-Baum, der dieses Element enthält und dessen Ordnung ''k'' beträgt. Ausgehend von ''X'' muss der Binomial-Baum, der das Element enthält, geeignet in kleinere Binomial-Bäume aufgespalten werden. Dieses Aufspalten des Baumes geschieht am einfachsten mit einer [[Rekursive Programmierung|rekursiven Funktion]] ''split'', der als Argument ein Knoten im Baum übergeben wird. Anfangs ist ''X'' selbst das Argument. Sofern das übergebene Argument einen Elternknoten besitzt, ruft sich die Funktion zuerst selbst mit diesem als Argument auf und entfernt anschließend solange das am weitesten links stehende Kind des Vaters – also das Kind mit höchster Ordnung – bis das Argument selbst aus dem Baum entfernt wurde.

Da das Entfernen des am weitesten links stehenden Elementes gerade die umgekehrte Operation zum oben dargestellten rekursiven Aufbau der Binomial-Bäume darstellt, sind die so abgespaltenen Bäume und der Rest weiterhin Binomial-Bäume. Ferner ist ''X'' nun Wurzel eines Baumes und es lässt sich zeigen, dass der ursprüngliche Baum nun in genau 2 Binomial-Bäume der Ordnung ''x'' sowie in jeweils einen Binomial-Baum der Ordnung ''x''+1, ''x''+2, ..., ''k-1'' zerfallen ist. Werden nun noch in gleicher Weise alle Kinder von ''X'' entfernt, so ist ''X'' vollständig isoliert und kann problemlos gelöscht werden. Dabei entsteht aus den Kindern für jedes ''j'' in {0, ..., ''x''-1} jeweils genau ein Binomial-Baum der Ordnung ''j''. Insgesamt bleibt also für jedes ''j'' aus {0, ..., ''k''-1} ein Binomial-Baum der Ordnung ''j'' übrig. Diese Bäume bilden zusammen wieder einen Binomial-Heap, der mittels ''merge'' mit dem Rest des Heaps verschmolzen werden kann.

Das Abspalten des am weitesten links stehenden Elementes ist in konstanter Zeit möglich. Da der ursprüngliche Baum genau ''k'' mal aufgespalten wird, der Binomial-Heap aber mindestens 2''k'' Elemente enthält, benötigt diese Operation im Worst-Case nur logarithmisch viel Zeit. Da das anschließende ''merge'' selbst auch nur logarithmisch viel Zeit benötigt ist auch die Gesamtlaufzeit im schlimmsten Fall logarithmisch zur Anzahl der Elemente im Heap.

=== Weitere Operationen ===
Die übrigen Operationen gestalten sich nun sehr einfach.

* Um ein neues Element einzufügen ''(insert)'', wird einfach ein neuer Heap erzeugt, der nur dieses eine Element enthält und dieser mittels ''merge'' mit dem eigentlichen Heap verschmolzen.
* Um ein Element mit minimalem Schlüssel zu entnehmen ''(extractMin)'', braucht lediglich das Minimum der Wurzeln gefunden zu werden, indem die Liste der Wurzeln einmal durchlaufen wird und das gefundene Element mit ''remove'' entfernt und zurückgegeben wird.
* Um den Schlüssel eines Elementes zu verändern ''(changeKey)'' wird dieses mit ''remove'' zunächst entfernt, dann dessen Schlüssel geändert und anschließend mit ''insert'' wieder eingefügt.

== Bemerkungen ==
Die Operationen ''remove'' und ''changeKey'' setzen voraus, dass die Position der entsprechenden Elemente im Heap bekannt ist. Im Allgemeinen ist es nämlich nicht möglich, effizient ein Element im Heap zu suchen. Daher muss die Operation ''insert'' einen [[Zeiger (Informatik)|Zeiger]] auf den Behälter für das eingefügte Element zurückliefern, den sich das aufrufende Programm im Bedarfsfall an geeigneter Stelle merkt.

Zu der hier dargestellten Implementierung gibt es noch eine Alternative. Diese gestattet aber nur das Verringern des Schlüssels eines Elementes. Entsprechend heißt die Operation dann nicht ''changeKey'', sondern ''decreaseKey''. Dabei wird statt ''remove'' die Operation ''decreaseKey'' direkt implementiert. Diese tauscht den Schlüssel einfach aus und stellt die Heap-Bedingung dadurch wieder her, dass Element und Schlüssel in den tragenden Behältern solange mit denen des Vaters getauscht werden, bis die Heap-Bedingung wieder erfüllt ist. Die Operation ''remove'' wird dann so implementiert, dass mit ''decreaseKey'' der Schlüssel des Elementes quasi unendlich klein gemacht wird, so dass das Element an die Wurzel seines Binomial-Baumes wandert. Anschließend können die Kinder der neuen Wurzel entfernt und mit ''merge'' wieder in den Baum eingefügt werden.

Problematisch an diesem Verfahren ist, dass nach einem ''decreaseKey'' die Zuordnung der Elemente zu ihren Behältern nicht mehr stimmt. Die Änderungen müssen dem aufrufenden Programm also noch irgendwie mitgeteilt werden.

== Literatur ==
* {{BibISBN|3486275151}}
* Jean Vuillemin: ''A data structure for manipulating priority queues''. ''Communications of the ACM'' '''21''', 1978, S. 309–314.

== Weblinks ==
* {{Internetquelle |url=https://www.eecs.yorku.ca/~aaw/legacy/Sotirios/BinomialHeap.html |titel=Simulation eines Binomial-Heaps |zugriff=2022-07-30}} ([[Java-Applet]], englisch)
* {{Internetquelle |url=http://olli.informatik.uni-oldenburg.de/BHeapA/Deutsch/Algorithmus.html |archiv-url=https://web.archive.org/web/20160313030913/http://olli.informatik.uni-oldenburg.de/BHeapA/Deutsch/Algorithmus.html |archiv-datum=2016-03-13 |zugriff=2022-07-30 |titel=Der Binomial Heap Algorithmus |titelerg=Lernprogramm zum Binomial Heap mit Animationen und interaktiven Aufgaben}} ([[Universität Oldenburg]])

{{Lesenswert|18. August 2005|8600444}}

[[Kategorie:Datenstruktur]]

Binomial-Heap - Versionsgeschichte

imported>Attraktor: Tote Weblinks repariert - beim 1. Link konnte ich das Java-Applet noch nicht testen