Binärer Heap vs Binomial Heap vs Fibonacci Heap, in Bezug auf die Leistung für eine Prioritätswarteschlange
https://stackoverflow.com/questions/8353038
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Könnte mir bitte jemand erklären, wie ich entscheiden soll, ob ich die eine oder andere Heap-Implementierung verwenden möchte, unter den im Titel genannten?
Ich möchte eine Antwort, die mich bei der Auswahl der Implementierung hinsichtlich der Leistung der Struktur entsprechend dem Problem unterstützt.Im Moment mache ich eine Prioritätswarteschlange, aber ich möchte nicht nur die am besten geeignete Implementierung für diesen Fall kennen, sondern auch die Grundlagen, die es mir ermöglichen, eine Implementierung in jeder anderen Situation auszuwählen ...
Eine andere zu berücksichtigende Sache ist, dass ich dieses Mal Haskell verwende. Wenn Sie also einen Trick oder etwas kennen, das die Implementierung mit dieser Sprache verbessern würde, lassen Sie es mich bitte wissen!Kommentare zur Verwendung anderer Sprachen sind jedoch nach wie vor willkommen!
Danke!und sorry, wenn die Frage zu einfach ist, aber ich bin überhaupt nicht mit Haufen vertraut.Dies ist das erste Mal, dass ich vor der Aufgabe stehe, eine zu implementieren ...
Nochmals vielen Dank!
Lösung
Den dritten Artikel finden Sie möglicherweise unter http://themonadreader.files.wordpress.com / 2010/05 / issue16.pdf relevant.
Andere Tipps
Zunächst werden Sie in Haskell keinen Standardheap implementieren. Sie implementieren stattdessen einen persistenten und funktionalen Heap. Manchmal sind die funktionalen Versionen klassischer Datenstrukturen genauso leistungsfähig wie das Original (z. B. einfache Binärbäume), manchmal jedoch nicht (z. B. einfache Warteschlangen). Im letzteren Fall benötigen Sie eine spezielle funktionale Datenstruktur.
Wenn Sie mit funktionalen Datenstrukturen nicht vertraut sind, empfehle ich, mit Okasakis großartigem Buch oder These (Kapitel von Interesse: mindestens 6.2.2, 7.2.2).
Wenn all das über Ihren Kopf ging, empfehle ich, mit der Implementierung eines einfachen verknüpften Binärhaufens zu beginnen. (Das Erstellen eines effizienten Array-basierten Binärheaps in Haskell ist etwas mühsam.) Sobald dies erledigt ist, können Sie versuchen, einen Binomialheap mithilfe von Okasakis Pseudocode zu implementieren oder sogar von vorne zu beginnen.
Sie haben unterschiedliche zeitliche Komplexität bei verschiedenen Vorgängen in der Prioritätswarteschlange. Hier ist eine visuelle Tabelle für Sie
╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║ Operation ║ Binary ║ Binomial ║ Fibonacci ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ insert ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ find Min ║ O(1) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Revmove ║ O(logN) ║ O(logN) ║ O(logN) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Decrease Key ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Union ║ O(N) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ■ Min element is root ║order k binomial tree Bk║ ■ Set of heap-ordered trees. ║
║ ║ ■ Heap height = logN ║ ■ Number of nodes = 2k.║ ■ Maintain pointer to min. ║
║ ║ ║ ■ Height = k. ║ (keeps find min/max O(1)) ║
║ ║ ║ ■ Degree of root = k. ║ ■ Set of marked nodes. ║
║ Useful ║ ║ ■ Deleting root yields ║ (keep the heaps flat) ║
║ Properties ║ ║ binomial trees ║ ║
║ ║ ║ Bk-1, … , B0. ║ ║
║ ║ ║ (see graph below) ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝
Ich habe dieses Bild von den Princeton-Vorlesungsfolien
Binomialheap:
Fibonacci-Haufen:
Hinweis: Binomial und Fibonacci Heap kommen mir bekannt vor, unterscheiden sich jedoch geringfügig:
- Binomialhaufen: Konsolidieren Sie eifrig Bäume nach jeder Einfügung.
- Fibonacci-Haufen: Verschieben Sie die Konsolidierung träge bis zum nächsten Lösch-Min.
Einige Verweise auf funktionale Binomial-Heaps, Fibonacci-Heaps und Pairing-Heaps: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
Wenn die Leistung wirklich das Problem ist, empfehle ich die Verwendung von Pairing Heap.Das einzige Risiko besteht darin, dass die Leistung bis jetzt noch eine Vermutung ist.Experimente zeigen jedoch, dass die Leistung recht gut ist.
