In der Informatik ist ein binomischer Haufen ein Haufen, der einem binären Haufen ähnlich ist, sondern auch unterstützt schnell das Mischen von zwei Haufen. Das wird durch das Verwenden einer speziellen Baumstruktur erreicht. Es ist als eine Durchführung des mergeable Haufen-Auszug-Datentyps wichtig (auch hat meldable Haufen genannt), der eine Vorzugswarteschlange ist, die Verflechtungsoperation unterstützt.

Binomischer Baum

Ein binomischer Haufen wird als eine Sammlung von binomischen Bäumen durchgeführt (vergleichen Sie sich mit einem binären Haufen, der eine Gestalt eines einzelnen binären Baums hat). Ein binomischer Baum wird rekursiv definiert:

• Ein binomischer Baum des Auftrags 0 ist ein einzelner Knoten
• Ein binomischer Baum des Auftrags k hat einen Wurzelknoten, dessen Kinder Wurzeln von binomischen Bäumen von Aufträgen k1, k2..., 2, 1, 0 (in dieser Ordnung) sind.

Ein binomischer Baum des Auftrags k hat 2 Knoten, Höhe k.

Wegen seiner einzigartigen Struktur kann ein binomischer Baum des Auftrags k von zwei Bäumen des Auftrags k1 trivial durch die Befestigung von einem von ihnen als das leftmost Kind der Wurzel der anderen gebaut werden. Diese Eigenschaft ist zur Verflechtungsoperation eines binomischen Haufens zentral, der sein Hauptvorteil gegenüber anderen herkömmlichen Haufen ist.

Der Name kommt aus der Gestalt: Ein binomischer Baum der Ordnung hat Knoten an der Tiefe. (Sieh Binomischen Koeffizienten.)

Struktur eines binomischen Haufens

Ein binomischer Haufen wird als eine Reihe binomischer Bäume durchgeführt, die die binomischen Haufen-Eigenschaften befriedigen:

• Jeder binomische Baum in einem Haufen folgt dem Eigentum des minimalen Haufens: Der Schlüssel eines Knotens ist größer oder gleich dem Schlüssel seines Elternteils.
• Es kann nur entweder ein oder binomische Nullbäume für jede Ordnung einschließlich der Nullordnung geben.

Das erste Eigentum stellt sicher, dass die Wurzel jedes binomischen Baums den kleinsten Schlüssel im Baum enthält, der für den kompletten Haufen gilt.

Das zweite Eigentum deutet an, dass ein binomischer Haufen mit n Knoten aus am grössten Teil des Klotzes n + 1 binomische Bäume besteht. Tatsächlich werden die Zahl und Ordnungen dieser Bäume durch die Zahl von Knoten n einzigartig bestimmt: Jeder binomische Baum entspricht einer Ziffer in der binären Darstellung der Nummer n. Zum Beispiel ist Nummer 13 1101 in der Dualzahl, und so wird ein binomischer Haufen mit 13 Knoten aus drei binomischen Bäumen von Aufträgen 3, 2, und 0 bestehen (sieh Zahl unten).

Durchführung

Weil keine Operation zufälligen Zugang zu den Wurzelknoten der binomischen Bäume verlangt, können die Wurzeln der binomischen Bäume in einer verbundenen Liste versorgt werden, die durch die Erhöhung der Ordnung des Baums bestellt ist.

Verflechtung

Wie oben erwähnt ist die einfachste und wichtigste Operation das Mischen von zwei binomischen Bäumen derselben Ordnung innerhalb von zwei binomischen Haufen. Wegen der Struktur von binomischen Bäumen können sie trivial verschmolzen werden. Da ihr Wurzelknoten das kleinste Element innerhalb des Baums, durch das Vergleichen der zwei Schlüssel ist, ist der kleinere von ihnen der minimale Schlüssel, und wird der neue Wurzelknoten. Dann wird der andere Baum ein Subbaum des vereinigten Baums. Diese Operation ist zum ganzen Mischen von zwei binomischen Haufen grundlegend.

fungieren Sie mergeTree (p, q)

wenn p.root.key

Die Operation, zwei Haufen zu verschmelzen, ist vielleicht am interessantesten und kann als ein Unterprogramm in den meisten anderen Operationen verwendet werden. Die Listen von Wurzeln von beiden Haufen werden gleichzeitig, ähnlich als im Verflechtungsalgorithmus überquert.

Wenn nur ein der Haufen einen Baum des Auftrags j enthalten, wird dieser Baum zum verschmolzenen Haufen bewegt. Wenn beide Haufen einen Baum des Auftrags j enthalten, werden die zwei Bäume zu einem Baum des Auftrags j+1 verschmolzen, so dass das Eigentum des minimalen Haufens zufrieden ist. Bemerken Sie, dass es später notwendig sein kann, diesen Baum mit einem anderen Baum der Gegenwart des Auftrags j+1 in einem der Haufen zu verschmelzen. Im Laufe des Algorithmus müssen wir höchstens drei Bäume jeder Ordnung untersuchen (zwei von den zwei Haufen, die wir verschmelzen und ein zusammengesetzter von zwei kleineren Bäumen).

Weil jeder binomische Baum in einem binomischen Haufen wenig in der binären Darstellung seiner Größe entspricht, gibt es eine Analogie zwischen dem Mischen von zwei Haufen und der binären Hinzufügung der Größen der zwei Haufen vom Recht-zu-link. Wann auch immer ein Tragen während der Hinzufügung vorkommt, entspricht das einem Mischen von zwei binomischen Bäumen während der Verflechtung.

Jeder Baum hat Ordnung am grössten Teil des Klotzes n, und deshalb ist die Laufzeit O (loggen Sie n).

fungieren Sie Verflechtung (p, q)

während nicht (p.end und q.end )

Baum = mergeTree (p.currentTree , q.currentTree )

wenn nicht heap.currentTree .empty

Baum = mergeTree (Baum, heap.currentTree )

heap.addTree (Baum)

sonst

heap.addTree (Baum)

heap.next p.next q.next

Einsatz

Das Einfügen eines neuen Elements zu einem Haufen kann durch das einfache Schaffen eines neuen Haufens getan werden, der nur dieses Element enthält und es dann mit dem ursprünglichen Haufen verschmilzt. Wegen der Verflechtung nimmt Einsatz O (loggen Sie n) Zeit jedoch hat es eine amortisierte Zeit von O (1) (d. h. unveränderlich).

Finden Sie minimal

Um das minimale Element des Haufens zu finden, finden Sie das Minimum unter den Wurzeln der binomischen Bäume. Das kann wieder leicht in O getan werden (loggen Sie n) Zeit, wie es gerade O gibt (loggen Sie n) Bäume und wurzeln folglich ein, um zu untersuchen.

Durch das Verwenden eines Zeigestocks zum binomischen Baum, der das minimale Element enthält, kann die Zeit für diese Operation auf O (1) reduziert werden. Der Zeigestock muss aktualisiert werden, wenn man jede Operation anders durchführt, als minimal Finden. Das kann in O getan werden (loggen Sie n), ohne die Laufzeit jeder Operation zu erheben.

Löschen Sie Minimum

Um das minimale Element vom Haufen zu löschen, finden Sie zuerst dieses Element, entfernen Sie es von seinem binomischen Baum, und erhalten Sie eine Liste seiner Subbäume. Dann gestalten Sie diese Liste von Subbäumen in einen getrennten binomischen Haufen durch die Umstellung sie vom kleinsten bis größte Ordnung um. Dann verschmelzen Sie diesen Haufen mit dem ursprünglichen Haufen. Da jeder Baum am grössten Teil des Klotzes n Kinder hat, ist das Schaffen dieses neuen Haufens O (loggen Sie n). Das Mischen von Haufen ist O (loggen Sie n), so löschen die kompletten minimale Operation, ist O (loggen Sie n).

fungieren Sie deleteMin (Haufen)

Minute = heap.trees .first

für jeden Strom in heap.trees

wenn current.root