簡介

priority_queue 是一個擁有權值觀念的 queue，它允許加入新的元素、移除舊的元素、查看 priority_queue 中權值之最的元素等功能。priority_queue 只允許在底端加入元素，并從頂端取出元素，除此之外沒有其它存取元素的途徑。

priority_queue 提供常數時間的最大元素(默認)查找，對數代價的插入與釋放。可為用戶提供的 compare 更改順序，例如，用 std::greater<T> 將導致最小元素作為 top() 出現。用 priority_queue 工作類似管理某些隨機訪問容器中的堆，優勢是不可能突然把堆非法化。

雖然priority_queue 的名字中帶有 queue，但是其底層的邏輯結構是堆。缺省情況下 priority_queue 利用一個大頂堆完成(底層存儲結構是 vector)。堆結構能滿足 priority_queue 所需要的”按照權值高低自動排序”的特性。這里要弄清楚的一點是：priority_queue 底層缺省使用 vector存 儲數據，這是它的存儲結構。而在邏輯上，它將序列視為一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的關系，在當前無序區間中選擇關鍵字最大(或最小)的元素。

最近刷leetcode題，使用了move()函數及優先隊列（堆）priority_queue數據結構，記錄一下！

1.move函數

move(obj)函數的功能是把obj當做右值處理，可以應用在對象的移動上。

右值引用

為了支持移動操作，新標準引入了一種新的引入類型——右值引用，所謂右值引用就是必須綁定到右值的引用。通過&&而不是&來獲得右值引用。

注意，如果僅僅是定義右值引用，那么obj本身不會被移走，在作為參數時會發生obj被移走：如下：

string str = "test";
    string&& r = move(str);
    cout<< r <<endl;
    cout<< str <<endl;
    string t(r);
    cout<< t <<endl;
    cout<< str <<endl;

運行結果：

?這時候r和str都可以使用。

但是，若左值不使用右值引用，move則會銷毀變量obj，之后都不能使用它，如：

string str = "test";
    string&& r = move(str);
    cout<< r <<endl;
    cout<< str <<endl;
    string t(move(r));
    cout<< t <<endl;
    cout<< str <<endl;

結果為：

?2.priority_queue隊列

優先隊列是一種容器適配器，采用了堆這樣的數據結構，保證了第一個元素總是整個優先隊列中最大的(或最小的)元素。

優先隊列默認使用vector作為底層存儲數據的容器，在vector上使用了堆算法將vector中的元素構造成堆的結構，所以其實我們就可以把它當作堆，凡是需要用堆的位置，都可以考慮優先隊列。

STL 中，priority_queue 容器適配器的定義如下：

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}

priority_queue 容器適配器模板類最多可以傳入 3 個參數，它們各自的含義如下：
typename T：指定存儲元素的具體類型；
typename Container：指定 priority_queue 底層使用的基礎容器，默認使用 vector 容器。(STL 序列式容器中只有 vector 和 deque 容器符合條件。)

typename Compare：指定容器中評定元素優先級所遵循的排序規則，默認使用std::less按照元素值從大到小進行排序，還可以使用std::greater按照元素值從小到大排序，但更多情況下是使用自定義的排序規則。

使用優先隊列創建大、小堆

//大根堆
priority_queue<int, std::deque<int>, std::greater<int>> values;
//默認是大根堆
priority_queue<int>values;
//小根堆
priority_queue<int, std::vector<int>, std::less<int>>values;

作為隊列有其隊列的成員函數

使用優先隊列，可以維護好最大/最小值；以及一些其他規則的一些比較（這個需要進行重載，目前還沒遇到）。

插入堆的時間復雜度最大為O(nlogn)。