Benutzer:APPER/Spielwiese

In der Informatik ist ein Binomial-Heap eine sehr spezielle Datenstruktur, also eine Art Datenelemente zu verwalten. Es handelt sich dabei um einen Art Heap: es können also Elemente mit beliebiger, festgelegter Priorität effizient in den Binomial-Heap eingefügt werden und jeweils das Element mit der höchsten Priorität entnommen werden. Damit eignen sie sich als Vorrangwarteschlange und ähneln somit binären Heaps, haben aber zusätzlich die Eigenschaft, dass zwei solcher Binominal-Heaps effizient zu einem vereinigt werden können. Dies ermöglicht es beispielsweise in einem Computersystem mit mehreren Prozessoren, anstehende, in einem Binominal-Heap gespeicherte Aufgaben von einem Prozessor zu einem anderen zu übertragen.

Die Priorität wird dabei in jedem Element durch einen Schlüssel gespeichert. Dementsprechend muss auf der Menge der Schlüssel (beispielsweise Ganze Zahlen) eine totale Ordnung bestehen (beispielsweise die Kleiner-Relation (<)), damit bei zwei Elementen jederzeit klar ist, welches Element das höherprioritätige ist.

Diese komplexe Datenstruktur wurde erstmals 1978 von Jean Vuillemin beschrieben.