如何獲取隊列的最小值和最大值？

您可以設計一個數據結構，就像一個包含'入隊'，'出隊''最小'和'最大'的隊列嗎？我知道一種使用2個堆棧分別查找最小值和最大值的方法，但我怎樣才能同時獲得這兩個值？如何獲取隊列的最小值和最大值？

由於

2012-09-17 xunzhang

在任何給定的棧或隊列中查找最小值和最大值都需要n的大O.這意味着你必須完成堆棧的完整迭代。 – Horus

這可能會幫助您設置正確的道路。 http://stackoverflow.com/questions/4077101/minmax-heap-algorithm-implementation –

的數據結構是公知的結構被稱爲優先級隊列。隊列中的每個元素都具有關聯的優先級，並且隊列保持高位到低位的排序順序。

隊列中的每個元素都必須帶有優先級，並且代碼必須維護訂單合同。

一些STL包含優先級隊列實現，但現在我看它，我不確定整個隊列是否保持優先順序。

2012-09-17 03:21:32 EvilTeach

不幸的是，我相信優先級隊列的設置使您能夠便宜地從剩餘的最高元素中選取。大多數實現不會讓您訪問最低的元素。有關STL接口的說明，請參見http://en.cppreference.com/w/cpp/container/priority_queue。 –

最小最大堆可以在常量時間http：//en.wikipedia中訪問最大和最小元素。org/wiki/Min-max_heap –

+1 to @PaulDixon。一個普通的std :: priority_queue <>不會在所有的基礎上做他想要的。 – WhozCraig

使用優先級隊列！

C++ STL

#include<queue>

通常，優先級隊列由二進制堆來實現。但它不能同時保持最大值和最小值。也許均衡搜索樹，如AVL，Splay或紅黑樹應該是更好的選擇。

2012-09-17 05:36:21 Yinyanghu

使用標準容器，像std::set這樣的完全有序的數據結構將提供對極端（例如，使用*s.begin()和*s.rbegin()。如果您有多個具有相同優先級的對象，則可能需要以任意方式斷開關係，或者使用std::multiset。

大多數實現可能會使用某種形式的red-black tree來實現這樣的集合。由於數據結構將始終保持排序，所以asymptotic performance可能比常規單端heap基於priority queue會給您帶來的更差，但對於許多應用程序來說，差異並不重要，因此實現自定義數據結構應該避免。

2012-09-17 06:15:05 MvG

通常使用某種heap structure來實現priority queue。有一種變化稱爲min-max heap，它允許恆定時間訪問最大和最小元素。已經有a question要求這種最小最大堆的C++實現。它的答案也應該對你有用。

This comment通過Paul Dixon首先提到的最小 - 最大堆，而this comment通過Chris Mansley指出，堆棧溢出的實現問題。

2012-09-18 14:55:38 MvG

回答