Unterschied zwischen einem Heap und einer Prioritätswarteschlange

36

Ich dachte immer, dass Haufen und Prioritäts - Warteschlangen Synonyme waren - eine abstrakte Datenstruktur , die unterstützt die insert, findMinund deleteMinOperationen.

Einiges an Literatur scheint mir zuzustimmen - zum Beispiel Chris Okasakis rein funktionale Datenstrukturen (Kapitel 3).

Auf der anderen Seite definiert Wikipedia die Heap- Seite als baumbasierte Datenstruktur und gibt an, dass Heaps eine konkrete Implementierung von Prioritätswarteschlangen sind.

Ich finde es schwierig, dies mit der Tatsache in Einklang zu bringen, dass ich mir mehr als eine Heap-Implementierung vorstellen kann - linke Heaps, Binomial-Heaps, Splay-Heaps ...

Bedeutet die einfache Tatsache, dass ein Heap mit verschiedenen Datenstrukturen implementiert werden kann, per Definition nicht, dass es sich um eine abstrakte Datenstruktur handelt? Und wenn dies der Fall ist, gibt es einen tatsächlichen Unterschied zu Prioritätswarteschlangen?

data-structures Nicolas Rinaudo
quelle
11
Lesen Sie die Wikipedia-Seite über Prioritätswarteschlangen ( en.wikipedia.org/wiki/Priority_queue ), auf der steht, "eine Prioritätswarteschlange kann mit einem Heap oder einer Vielzahl anderer Methoden wie einem ungeordneten Array implementiert werden" - und das ist tatsächlich die Antwort auf diese Frage Ihre Frage.
Doc Brown
2
Nun, nicht wirklich - es hilft mir nicht zu verstehen, ob ein Heap eine konkrete oder eine abstrakte Datenstruktur ist. Ich würde eher von einer abstrakten Rede sprechen, da es viele konkrete Implementierungen eines Haufens gibt. Wenn dies der Fall ist und eine Prioritätsliste und ein Heap abstrakte Datenstrukturen mit denselben Eigenschaften sind, muss ich den Unterschied verstehen und sagen, dass eine mögliche Implementierung der anderen nicht besonders hilfreich ist, wenn keine von beiden tatsächlich eine ist konkrete Umsetzung.
Nicolas Rinaudo
Noch schlimmer ist es: Ein binärer Heap kann als Array oder als binärer Baum implementiert werden. Zum Glück habe ich noch nichts von einem Array gehört, das als etwas anderes implementiert wurde.
Alexey

Antworten:

25

Eine Prioritätswarteschlange kann eine beliebige Implementierung haben, z. B. ein Array, das Sie beim Aufrufen linear durchsuchen. Alles, was es bedeutet, ist, dass Sie beim Pop entweder den minimalen oder den maximalen Wert erhalten.

Ein klassischer Haufen, wie er normalerweise genannt wird, ist normalerweise ein kleiner Haufen. Eine Implementierung, die eine gute zeitliche Komplexität ( O(log n)bei Push und Pop) und keinen Speicheraufwand aufweist.

Ratschenfreak
quelle
4
Wollen Sie damit sagen , dass der Unterschied , dass, während sie die gleichen Operationen (teilen findMin, deleteMin, insert), haben Haufen garantiert „gut“ Komplexität für sie , wo Prioritäts - Warteschlangen nicht?
Nicolas Rinaudo
Kann Heap nicht auch unterschiedliche Implementierungen mit unterschiedlichen Zeitkomplexitäten haben (zum Beispiel ein gewöhnlicher verknüpfter Binärbaum)? Die zeitliche Komplexität hängt auch vom verwendeten Speicher ab. Wenn es sich um ein Magnetband handelt, gibt es O(log(n))vermutlich kein Push-and-Pop-Band.
Alexey
6

Diese Website bietet eine wirklich klare Erklärung. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

Kurz gesagt, eine Prioritätswarteschlange kann unter Verwendung vieler der Datenstrukturen implementiert werden, die wir bereits untersucht haben (ein Array, eine verknüpfte Liste oder ein binärer Suchbaum). Diese Datenstrukturen bieten jedoch nicht die effizientesten Operationen. Um alle Operationen sehr effizient zu gestalten, verwenden wir eine neue Datenstruktur, die als Heap bezeichnet wird.

Chihung Yu
quelle
1
Beachten Sie, dass in der Zusammenfassung der Seite, mit der Sie verknüpft sind, die Prioritätswarteschlange selbst als Datenstruktur bezeichnet wird .
Alexey
2

Ich denke, dass das, was Sie über Beton vs. Abstrakt geschrieben haben, richtig ist. Wenn Sie sagen, dass Splay-Heaps und Binomial-Heaps unterschiedliche Implementierungen von Heaps sind, ist es meines Erachtens richtiger zu sagen, dass es sich um unterschiedliche Arten von Heaps handelt. Heap halte ich für eine Implementierungskategorie, die in der Regel nicht nur die gleiche Schnittstelle, sondern auch die gleichen Zugriffszeiten garantiert.

Sie sehen dies auch bei assoziativen Maps, Hash-Tabellen und binären Suchbäumen. Bsts- und Hash-Tabellen sind beide konkrete Datenstrukturen, die die assoziative Map-Abstract-Schnittstelle bereitstellen. Rot-Schwarz-Bäume und AVL-Bäume sind beide ausgeglichene BSTs mit denselben großen O-Garantien und derselben zusätzlichen Schnittstelle (in der Reihenfolge des Durchlaufens). Es sind verschiedene Arten von Bäumen. Ich würde mehr sagen als verschiedene Implementierungen von Bäumen. Es handelt sich um verschiedene, aber eng verwandte Implementierungen von assoziativen Karten.

Nir Friedman
quelle