簡介

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

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

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

最近刷leetcode題，使用了move()函數(shù)及優(yōu)先隊列（堆）priority_queue數(shù)據(jù)結(jié)構(gòu)，記錄一下！

1.move函數(shù)

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

右值引用

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

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

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

運行結(jié)果：

?這時候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;

結(jié)果為：

?2.priority_queue隊列

優(yōu)先隊列是一種容器適配器，采用了堆這樣的數(shù)據(jù)結(jié)構(gòu)，保證了第一個元素總是整個優(yōu)先隊列中最大的(或最小的)元素。

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

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

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

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

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

使用優(yōu)先隊列創(chuàng)建大、小堆

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

作為隊列有其隊列的成員函數(shù)

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

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