什麼時候應該使用make_heap與優先級隊列？

Question

我有一個我想用來創建堆的矢量。我不確定是否應該使用C++ make_heap函數或將我的向量放在優先級隊列中？在性能方面哪個更好？我應該什麼時候使用一個與另一個？

Answer 1

性能溫度沒有差別。 std::priority_queue只是一個適配器類，它將容器和與堆相關的函數調用包裝到一個類中。 std::priority_queue的規範公開聲明。

通過從暴露的std::vector（通過直接調用與堆相關的函數）構建一個基於堆的優先級隊列，您可以保持對外部訪問的可能性的打開，可能會損壞堆/隊列的完整性。 std::priority_queue充當限制訪問「規範」最小值的障礙：push(),pop()，top()等。您可以將其視爲自律執行措施。另外，通過使您的隊列接口適應「規範」操作集，您可以使其與基於相同外部規範的其他基於類的優先級隊列實現相互統一併可互換。

Answer 2

priority_queue（至少通常）是作爲堆實現的。因此，真正的問題是priority_queue是否提供您所需要的。當你使用make_heap時，你仍然可以訪問所有元素。當你使用priority_queue時，只有少數幾個操作對元素進行非常有限的訪問（基本上只需插入一個項目，然後刪除隊列頭部的項目）。

Answer 3

priority_queue不是容器。它是使用特定底層容器的容器適配器，例如vector或deque，並提供一組特定的方法來處理數據。而且，它的實現依賴於*_heap算法。

例如，無論您何時將新值推送到vector，您都應該撥打push_heap來擴展視爲堆的範圍。如果您不使用priority_queue，它可以讓您考慮vector的一半（std::make_heap(v.begin(), v.begin() + (v.size()/2))），而另一半則爲原樣。

什麼priority_queue確實，當你調用它的push：它推動了新的元素基礎容器的後面，並呼籲push_heap保持優先級堆屬性（只在乎的第一個元素是最大的）。

我會說你最好考慮解決方案的設計和你的具體要求，而不是性能問題。

Answer 4

如果你不想修改那個向量，那麼你應該使用優先級隊列，因爲它會創建一個單獨的向量（需要額外的空間）。而且，它很容易實現。例如，當你在使用make_heap的同時彈出一個元素時，你必須使用兩個命令，首先是pop_heap，然後是pop_back ..但是如果是優先級隊列，只需一個命令即可。同樣，將元素推入堆中。
現在，兩者的性能都是相同的，因爲優先級隊列不是容器，它使用一些底層容器作爲矢量或deque，它使用make_heap操作所使用的相同堆操作。因此，您應該根據您的要求。