Wann sollte make_heap vs. Priority Queue verwendet werden?

Question

Ich habe einen Vektor, den ich verwenden möchte, um einen Heap zu erstellen. Ich bin mir nicht sicher, ob ich die C++ make_heap-Funktion verwenden oder meinen Vektor in eine Prioritätswarteschlange stellen sollte. Was ist besser in Bezug auf die Leistung? Wann sollte ich eins gegen das andere benutzen?

Answer 1

Es gibt keinen Unterschied in der Leistung. std::priority_queue ist nur eine Adapterklasse, die den Container und die gleichen Heap-bezogenen Funktionsaufrufe in eine Klasse umschließt. Die Spezifikation der std::priority_queue besagt dies offen.

Durch Erstellen einer Heap-basierten Prioritätswarteschlange von einem exponierten std::vector (durch direktes Aufrufen von Heap-bezogenen Funktionen) halten Sie die Möglichkeit des Zugriffs von außen offen, wodurch die Integrität des Heap/Queue potenziell beschädigt wird. std::priority_queue wirkt als eine Barriere, die diesen Zugang auf ein "kanonisches" Minimum beschränkt: push(), pop(), top() usw. Sie können es als Selbstdisziplin durchsetzende Maßnahme sehen.

Durch die Anpassung Ihrer Warteschlangenschnittstelle an den "canonical" Satz von Operationen können Sie ihn außerdem einheitlich und austauschbar mit anderen klassenbasierten Implementierungen von Prioritätswarteschlangen machen, die derselben externen Spezifikation entsprechen.

Answer 2

Eine priority_queue ist (zumindest normalerweise) als Heap implementiert. Daher ist die eigentliche Frage, ob eine priority_queue bietet, was Sie brauchen. Wenn Sie make_heap verwenden, haben Sie weiterhin Zugriff auf alle Elemente. Wenn Sie priority_queue verwenden, haben Sie nur wenige Operationen, die sehr begrenzten Zugriff auf Elemente haben (im Grunde nur ein Element einfügen und das Element am Anfang der Warteschlange entfernen).

Answer 3

priority_queue ist kein Container. Es ist ein Containeradapter, der einen spezifischen darunterliegenden Container verwendet, z. vector oder deque, und bietet eine bestimmte Reihe von Methoden für die Arbeit mit den Daten. Darüber hinaus beruht seine Implementierung auf den *_heap Algorithmen.

Zum Beispiel, wenn Sie einen neuen Wert auf vector drücken, sollten Sie push_heap aufrufen, um einen Bereich zu erweitern, der als Heap betrachtet wird. Wenn Sie nicht die priority_queue verwenden, können Sie beispielsweise die Hälfte der vector als Heap (std::make_heap(v.begin(), v.begin() + (v.size()/2))) betrachten, während eine andere Hälfte unverändert ist.

Was priority_queue tut, wenn Sie push auf ihn nennen: es drückt ein neues Element auf die Rückseite des darunter liegenden Behälters und ruft push_heap die Heap-Eigenschaft zu halten priorisiert (es zählt nur das erste Element die größten zu sein).

Ich würde sagen, dass Sie eher das Lösungsdesign und Ihre spezifischen Anforderungen als Leistungsprobleme berücksichtigen sollten.

Answer 4

Wenn Sie diesen Vektor nicht ändern möchten, sollten Sie die Prioritätswarteschlange verwenden, da sie einen separaten Vektor erstellt (benötigt zusätzlichen Platz). Darüber hinaus ist es einfach zu implementieren. Wenn Sie zum Beispiel make_heap verwenden, während Sie ein Element aufrufen, müssen Sie zwei Befehle verwenden: zuerst pop_heap und dann pop_back .. Sie können dies jedoch mit nur einem Befehl im Falle einer Prioritätswarteschlange tun. Ähnlich, während Sie das Element in den Haufen schieben.
Jetzt wäre die Leistung von beiden gleich, weil die Prioritätswarteschlange kein Container ist und einige zugrunde liegende Container als Vektor oder Deque verwendet, die dieselben Heap-Operationen wie von make_heap operations verwenden. Sie sollten also je nach Ihren Anforderungen einen verwenden .