Unterschied zwischen std :: set und std :: priority_queue

Question

Da sowohl std::priority_queue und std::set (und std::multiset) sind Datencontainer, die Elemente speichern und lassen Sie sie in einer geordneten Art und Weise zuzugreifen, und haben gleiche Einfügungs Komplexität O(log n), was sind die Vorteile der Verwendung von einer über die andere (oder, welche Art von Situationen erfordern die eine oder andere?)?

Während ich weiß, dass die zugrunde liegenden Strukturen unterschiedlich sind, bin ich nicht so viel Interesse für den Unterschied in der Umsetzung als ich im Vergleich bin ihr Leistung und Eignung für verschiedene Anwendungen.

Hinweis: Ich weiß über die No-Duplikate in einem Satz. Deshalb habe ich auch std::multiset erwähnt, da es genau das gleiche Verhalten wie die std::set hat, aber verwendet werden kann, wenn die gespeicherten Daten als gleiche Elemente verglichen werden dürfen. Also, bitte, kommentieren Sie nicht das Problem mit einzelnen/mehreren Schlüsseln.

Answer 1

Eine Prioritätswarteschlange nur Sie in sortierter Reihenfolge Zugriff auf ein Element gibt - das heißt, können Sie die höchste Priorität Einzelteil erhalten, und wenn Sie das entfernen, können Sie die nächsthöchste Priorität erhalten, und so weiter. Eine Prioritätswarteschlange erlaubt auch doppelte Elemente, also ist es mehr wie ein Multiset als ein Set. [Edit: Wie @Tadeusz Kopec darauf hingewiesen hat, ist das Erstellen eines Heaps auch linear auf die Anzahl der Elemente im Heap, wobei das Erstellen einer Menge O (N log N) ist, es sei denn, sie wird aus einer bereits bestellten Sequenz erstellt es ist auch linear).]

Ein Set ermöglicht Ihnen vollen Zugriff in sortierter Reihenfolge, so können Sie zum Beispiel zwei Elemente irgendwo in der Mitte des Sets finden, dann in der Reihenfolge von einem zum anderen traversieren.

Answer 2

set/multiset werden in der Regel von einem Binärbaum unterstützt. http://en.wikipedia.org/wiki/Binary_tree

priority_queue wird im Allgemeinen von einem Heap unterstützt. http://en.wikipedia.org/wiki/Heap_(data_structure)

Also die Frage ist wirklich wann sollten Sie einen binären Baum anstelle eines Heaps verwenden?

Beide Strukturen sind in einem Baum angeordnet, jedoch sind die Regeln über die Beziehung zwischen Anstichen unterschiedlich.

Wir werden die Positionen P für Eltern, L für das linke Kind und R für das rechte Kind aufrufen.

In einem binären Baum L < P < R.

In einem Haufen P < L und P < R

So Binärbäumen sort "seitwärts" und jede Art "nach oben".

Also, wenn wir dies als ein Dreieck betrachten, als im binären Baum L, sind P, R vollständig sortiert, während im Haufen die Beziehung zwischen L und R unbekannt ist (nur ihre Beziehung zu P).

Dies hat folgende Auswirkungen:

• Wenn Sie eine unsortierte Array haben und wollen, dass es in einen binären Baum drehen dauert es O(nlogn) Zeit. Wenn Sie es in einen Haufen machen möchten, dauert es nur O(n) Zeit, (wie es nur das extreme Element zu finden ist)

• Heaps sind effizienter, wenn Sie nur das extreme Element (niedrigste oder höchste von einigen Vergleichsfunktion). Heaps machen nur die Vergleiche (faul), die notwendig sind, um das extreme Element zu bestimmen.

• Binärbäume führen die Vergleiche durch, die erforderlich sind, um die gesamte Sammlung zu ordnen, und behalten die gesamte Sammlung ständig sortiert.

• Heaps haben konstante Zeit (Peek) des untersten Elements, binäre Bäume haben logarithmische Zeit des niedrigsten Elements.

Answer 3

std::priority_queue ermöglicht folgendes zu tun:

1. Legen Sie ein Element O(log n)
2. Holen Sie sich das kleinste Element O(1)
3. Löschen des kleinste Element O(log n)

während std::set hat Weitere Möglichkeiten:

1. Legen Sie ein beliebiges Element O(log n) und die Konstante größer als in std::priority_queue
2. Finden jede Element O(log n)
3. ein Element finden,> = als das Ihre für O(log n) (lower_bound) suchen
4. Erase jedes Element O(log n)
5. zum vorherigen/nächsten Elemente in sortierter Reihenfolge O(1)
6. Holen Sie sich das kleinste Element O(1)
7. das größte Element O(1)

Holen beide

Answer 4

Seit std::priority_queue und std::set (und std::multiset) sind Datencontainer, die Elemente speichern und ermöglicht es Ihnen, auf sie zuzugreifen in einer geordneten Art und Weise und haben die gleiche Komplexität der Einfügung O(log n), was sind die Vorteile der Verwendung von einem über den anderen (oder, welche Art von Situationen fordern die eine oder andere das andere?)?

Obwohl Einsatz und erase Operationen für beide Behälter haben die gleiche Komplexität O (log n), diese Operationen für std :: eingestellt sind langsamer als für std :: priority_queue . Das liegt daran, Std :: Set macht viele Speicherzuordnungen.Jedes Element von Std :: Set ist bei einer eigenen Zuordnung gespeichert. std :: priority_queue (mit Unterlegen Std :: Vektor Container standardmäßig) verwendet einzelne Zuordnung, um alle Elemente zu speichern. Andererseits verwendet std :: priority_queue viele Swap-Operationen auf seinen Elementen, während Std :: Set nur Zeiger Swapping verwendet. Wenn also der Swapping-Vorgang für den Elementtyp sehr langsam ist, kann die Verwendung von std :: set effizienter sein. Außerdem kann das Element überhaupt nicht ausgetauscht werden.

Speicheraufwand für Std :: Set ist viel größer, auch weil es viele Zeiger zwischen seinen Knoten speichern muss.