爲什麼std :: priority_queue使用max heap而不是min heap？

我總是想知道爲什麼STL優先級隊列默認使用max堆而不是min堆。想到兩個明顯的用例是尋路（Dijkstra）和建立霍夫曼代碼。這兩種算法都需要先拉出最小元素。默認情況下，由於排序（std :: sort）使用升序排列，所以我想知道priority_queue，背後的設計原因是什麼，因爲默認情況下我非常喜歡min堆。爲什麼std :: priority_queue使用max heap而不是min heap？

來源

2014-08-31 mar

因爲它基本上是*優先級隊列*，而不是堆。 – 2014-08-31 09:18:37

可能是因爲在優先級隊列中，您希望優先級較高的項目先到達，但我同意這不是一個考慮周全的設計（因爲它實際上要求每個人都向後執行比較）。相反，擁有某種優先級對象來實現其比較運算符會更有意義，因爲較高優先級的值「低於」低優先級值。 – 2014-08-31 09:19:41

@MichaelAaronSafyan：即使「優先」也是令人困惑的，因爲人們說「這項任務是優先考慮的事情1」，他們的意思是「先做」，而不是「最後做」。普通人對優先級的理解是，「最高」優先級是最小的優先級，接下來是「第二優先級」......我同意OP在STL中做出的選擇似乎很愚蠢，但也許這裏沒有人真正知道*爲什麼這樣做。 – 2014-08-31 11:28:02

有一個原因，但它是與C++的相互關聯的功能。

priority_queue被設計爲圍繞make_heap,pop_heap和push_heap的易於使用的包裝。堆函數將最大值保留在前端是合理的，因爲這是您需要實現的功能sort_heap，它也使用堆函數。

當然，您可以始終使用greater實例化priority_queue而不是less以獲得所需的行爲。

來源

2015-02-17 21:24:50

那麼，爲什麼'make_heap'默認情況下最大堆而不是最小堆？實際上，'sort_heap'可以通過max heap或min heap來實現。 – 2016-06-24 08:50:29

Priority_queue從make_heap/pop_heap/push_heap/sort_heap改編而來。當你使用更少的make_heap時，元素按升序排序。最後一個元素被視爲根元素。所以它是最大的堆。我想有兩個原因：

我們總是使用較少的所有默認STL排序。
push_back（）或pop_back（）比push_front（）或pop_front（）效率高得多。

來源

2017-06-09 23:09:58

爲什麼std :: priority_queue使用max heap而不是min heap？

回答

相關問題