04.03.2020
Falls sie meine Seite über den binären Heap noch nicht kennen, das ist der empfohlene Startpunkt um Heaps kennenzulernen. Der binäre Heap ist der einfachste Heap den man sich ausdenken kann, aber kompliziertere Heaps haben für viele Anwendungen eine bessere Charakteristik. Diese Seite zeigt den Binomial-Heap, eine solche Datenstruktur. Er dient dem selben Zweck wie der binäre Heap, nämlich das geringste (oder größte) Element herauszunehmen, während stetig neue Elemente eingefügt werden. So kann der Heap zum Beispiel als Vorrangwarteschlange benutzt werden. Obwohl Heaps mehr als nur diese beiden Operationen unterstützen, illustrieren sie die Funktionsweise ganz gut. Hier werde ich die mathematischen Performanzaspekte mal beiseite lassen und dafür den Betrieb des Binomial-Heaps durch Animationen zeigen, wie sonst auch. Der Hauptvorteil des Binomial-Heaps gegenüber dem binären Heap ist, dass das Zusammenfügen von mehreren Heaps schneller abläuft, der Vorteil des binären Heaps hingegen ist dafür die einfache Umsetzung.
Dieses Panel zeigt die Operationen Einfügen und Entfernen des geringsten Elements auf einem Binomial-Heap. Die Kreise repräsentieren Knoten im Heap, die eingefügte Zahlen enthalten.
Ein Binomial-Heap, anders als der binäre Heap, besteht aus nicht nur einem Baum, sondern einem ganzen Wald von Heap-geordneten Bäumen. Wie viele Bäume vorhanden sind hängt von der größe des Heaps ab, gelegentlich kann es aber nur ein einzelner sein. Jeder dieser Bäume unterliegt der Heapordnung, was bedeutet das ein Elternknoten einen geringeren oder gleichen Wert wie ein Kindknoten hat, wie in den Heaps auf dieser Seite der Fall ist. Es ist auch möglich die umgekehrte Ordnung zu wählen, bei der die Eltern einen größeren oder gleichen Wert haben wie die Kinder. Das obige Panel zeigt die Heapordnung für jeden Knoten auf den geklickt wird. Man beachte, dass die Heapordnung nur innerhalb jeden Baumes gilt, und die Wurzelknoten untereinander keine besondere Beziehung haben müssen.
Der Binomial-Heap besteht aus Binomial-Bäumen, die oben in verschiedenen Größen gezeigt werden. Diese folgen bestimmten Regeln, die dann mathematische Eigenschaften hervorrufen. Der Rang des Baumes ist gegeben durch die Anzahl der Kinderknoten der Wurzel, und ist gleich der Tiefe des Baumes unter dem Wurzelknoten, runter bis zum untersten Knoten. Die Anzahl der Knoten auf jeder Ebene des Baumes ist durch die Binomial-Koeffizienten gegeben, die rechts neben dem Baum gezeigt werden. Hiervon rührt übrigens der Name des Binomial-Heaps. Die Gesamtzahl an Elementen (n) im Baum ist immer eine Zweierpotenz und ist gleich der Summe der Koeffizienten.
Ein neues Element in den Binomial-Heap einzufügen ist ziemlich einfach. Erst wird die Zahl in einen neuen Knoten gepackt, der dann in einen separaten ein-elementigen Baum platziert wird, der in den Heap kommt. Dann werden die Bäume vom kleinsten zum größten durchlaufen und der Heap-Algorithmus stellt sicher, dass höchstens einer von jeder Größe vorkommt. Falls es zwei Bäume gleichen Ranges und damit der selben Größe gibt, werden sie zu einem Baum zusammengeführt. Hierbei muss die Heapordnung erhalten werden, dies wird erreicht indem der größere der alten Wurzelknoten unter dem kleineren platziert wird, der somit der Wurzelknoten des neuen Baumes wird. Die Prozedur wird dann für den nächstgrößeren Baum wiederholt, wobei wieder sichergestellt wird, dass es höchstens einen Baum dieser Größe gibt. Diese Prozedur endet nach einer endlichen Zahl von Schritten und die Ordnung des Binomial-Heaps ist wiederhergestellt.
Die Anordnung von Bäumen im Binomial-Heap korrespondiert zu den Stellen in der binären Darstellung der Zahl der Knoten im Heap. Das Vorhandensein eines Baumes einer gewissen Größe wird durch eine 1 oder 0 in der Zahl dargestellt. Die Binärzahl für den gezeigten Heap wird unter dem Panel angezeigt.
Das minimale Element zu entfernen ist nur unwesentlich komplizierter als das Einfügen eines neuen Knotens. Zuerst wird der kleinste Wurzelknoten unter den Bäumen des Heaps identifiziert und entfernt. Dieser ist auch der geringste Knoten des gesamten Heaps, da jeder Wurzelknoten der geringste Knoten in seinem Baum ist. Die resultierenden verwaisten Unterbäume unter der alten Wurzel werden dann als separate Bäume zurück in den Heap überführt. Wie zuvor besteht der nächste Schritt darin sicherzustellen das es höchstens einen Baum von jedem Rang im Heap gibt. Dies bedeutet leicht mehr Aufwand als im Falle des Einfügens, da wir mehr als einen neuen Baum in den Heap eingefügt haben. Aber mit genug Zeit fügt der Heap-Algorithmus Bäume zusammen bis die Heapordnung wiederhergestellt ist.
Das obige Panel zeigt Binomial-Heaps in einem anderen Darstellungsmodus. Die Knoten sind kleiner als zuvor, so das die Zahlen nicht mehr dargestellt werden können, stattdessen wird die Größe der Zahl durch die Färbung des Knotens dargestellt, wobei hellere Schattierungen kleinere Zahlen repräsentieren. So passen größere Heaps in die Darstellung und können gezeigt werden. Wir haben auch die Geschwindigkeit erhöht, und es wird wieder der Heap bis zu einer gewissen Größe aufgefüllt, und dann wird das geringste Element nach und nach aus dem Heap entfernt bis dieser wieder leer ist.
Wie bereits erwähnt ist ein Vorteil von Binomial-Heaps gegenüber binären Heaps die Geschwindigkeit mit der Heaps zusammengeführt werden. Hierbei bedeutet Zusammenführen das Fusionieren von Heaps zu einem einzigen größeren Heap. Dies wird oben gezeigt, wo der obere blaue Heap und der untere grüne Heap zu einem zusammengeführt werden. Dies wird erreicht indem die Bäume des erste Heaps in den zweiten einzeln eingefügt werden, und dann wird die Heapordnung wie zuvor wiederhergestellt.
Bald präsentieren wir hier einen weiteren Typ des Heaps, den Fibonacci-Heap.