Binomial-Heap

In der Informatik ist ein Binomial-Heap eine Datenstruktur, genauer ein Heap, der sich, ähnlich wie binäre Heaps, als Vorrangwarteschlange einsetzen lässt. Das heißt, dass in beliebiger Reihenfolge 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 Prozessors einem anderen zu übertragen.

Die Priorität der Elemente wird diesen durch 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 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-Heaps. Diese besitzen 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-Algorithmen eignen.