Binomial Heap hat ein ganz besonderes Design. Persönlich glaube ich nicht, dass dieses Design intuitiv ist.
Obwohl Beiträge wie Was ist der Unterschied zwischen Binäre Haufen und Binomialhaufen? spricht über diff und seine Spezialität, ich frage mich immer noch, wann ich es verwenden sollte.
In Ссылка heißt es
Wegen seiner einzigartigen Struktur kann ein Binomialbaum der Ordnung k sein konstruiert aus zwei Bäumen der Ordnung k-1 trivial durch Anfügen eines von sie als das am weitesten links liegende Kind der Wurzel des anderen. Diese Funktion ist von zentraler Bedeutung für die Zusammenführung eines Binomialspeichers, der sein Hauptteil ist Vorteil gegenüber anderen konventionellen Haufen.
Ich nehme an, dass ein Vorteil von Binomial Heap seine Zusammenführung ist. % Co_de% hat jedoch auch O (logN) merge und viel einfacher, warum verwenden wir immer noch Binomial Heap? Wann sollte ich Binomial Heap verwenden?
Bearbeiten
Eine der eigentlichen Fragen, die ich hier stellen möchte, ist Was ist genau der Vorteil von Binomial Heap ?
Der Artikel für den linken Baum lautet:
Beim Einfügen eines neuen Knotens in einen Baum wird ein neuer Baum mit einem Knoten erstellt und in den vorhandenen Baum eingefügt. Um ein minimales Element zu löschen, entfernen wir das Root und die linken und rechten Subbäume werden dann zusammengeführt. Beide Operationen benötigen O (log n) -Zeit. Für Insertionen ist dies langsamer als binominale Heaps, die die Insertion in der amortisierten konstanten Zeit O (1) und O (log n) Worst-Case unterstützen.
So scheint es, dass der Vorteil des Binomial-Heaps darin besteht, dass die Einfügungen schneller sind.
Zumindest sagt uns das eine Analyse der Asymptotik. Die Laufzeit der realen Welt ist etwas ganz anderes und hängt, wie Gene in seiner Antwort sagte, von konstanten Faktoren ab. Die einzige Möglichkeit, zu bestimmen, welche für Ihre Anwendung besser ist, besteht darin, sie zu testen.
Es gibt keine allgemeine Antwort auf Ihre Frage.
Der konstante Faktor in der Laufzeitbeziehung zur Datengröße für solche Algorithmen auf Bibliotheksebene bestimmt oft, welche Auswahl getroffen werden soll. Wenn zum Beispiel eine O (1) -Operation einen Faktor 20 mal langsamer ist als ein O (log n), wenn n = 1 ist, ist es besser, den O (log n) -Algorithmus für n & lt; 1.000.000.
Die Schlussfolgerung ist, dass asymptotische Zeitgrenzen nur ein Anhaltspunkt sind. Sie würden eher Binomial als Linkshaufen verwenden, wenn
Hinzugefügt Als Reaktion auf die Bemerkung des OP, dass er nach Motivation sucht: Ich kann nicht für den Autor dieses Algorithmus sprechen. Aber im Allgemeinen finden Algorithmenentwickler neue, schöne Ansätze und veröffentlichen sie, selbst wenn der Vorteil, den sie bieten, marginal oder rein theoretisch ist.
Das ist gut. So geht die Informatik voran. Der Ansatz kann sich in anderen Einstellungen auch dann auszahlen, wenn das Problem nicht groß ist.
Ein (altes) Beispiel hierfür sind Sprunglisten, die 1989 entwickelt wurden, um das gleiche Problem mit fast der gleichen Effizienz zu lösen wie ausgewogene binäre Suchbäume, die 1962 oder früher bekannt waren. Warum die Mühe? Weil wir können.
Tags und Links algorithm data-structures