優(yōu)先隊列（priority_queue）

? ?優(yōu)先隊列是一種特殊的隊列，它同一般隊列一樣，都支持先入先出的規(guī)則，但不同于一般隊列的是，它對存儲的數(shù)據(jù)有著自己獨特的存儲風(fēng)格。

priority_queue<int>pa;pa.push(1);pa.push(2);pa.push(3);pa.push(4);pa.push(5);int n = pa.size();for (int i = 0;i <n ;i++){cout << pa.top() << " ";pa.pop();}cout << endl;return 0;

代碼運行結(jié)果為 5, 4, 3, 2, 1，由此可見，我們發(fā)現(xiàn)優(yōu)先隊列中的數(shù)據(jù)按一定的規(guī)則排序?

?

優(yōu)先隊列是一個模板類，擁有三個模板參數(shù)

1. T為存儲的數(shù)據(jù)類型
2. Container為容器，如list，vector等，決定了優(yōu)先隊列中數(shù)據(jù)的存儲方式
3. Compare為比較方法，?它對存儲的數(shù)據(jù)進(jìn)行排序提供比較方法

優(yōu)先隊列的模板參數(shù)中，除了第一個數(shù)據(jù)類型沒有缺省值，其他兩個均有缺省值，也代表在實際使用中，我們不顯示寫出后兩個模板參數(shù)也可以。?

優(yōu)先隊列會對每一個存進(jìn)的數(shù)據(jù)進(jìn)行排序，這類似于我們之前學(xué)習(xí)的一個數(shù)據(jù)結(jié)構(gòu)，也就是堆，它會對新加入的數(shù)據(jù)元素進(jìn)行向上調(diào)整，也是排序，堆有大堆和小堆，同樣，優(yōu)先隊列也有。

priority_queue<int>q;//大堆
priority_queue<int, vector<int>, less<int>> q; // 大堆
priority_queue<int, vector<int>, greater<int>> q; // 小堆

less代表的是大堆，greater代表的是小堆，和我們?nèi)粘５恼J(rèn)知相違背，我們記住就好，c++就是這么定義的（less和greater是c++中的兩個比較函數(shù)）

?優(yōu)先隊列的接口

1. ?top（）取出隊頭元素
2. pop（）刪除隊頭元素
3. push（）添加隊元素，并按照一定比較方法，與前面的數(shù)據(jù)比較，找到自己的新位置
4. empty（）判斷優(yōu)先隊列是否為空

?優(yōu)先隊列的實現(xiàn)

namespace Yu
{template<class T>class Less//我要用這個仿函數(shù)建立大堆，契合c++，父親大于孩子{public:bool operator()(T& x, T& y){return x < y;}};template<class T>class Great//用這個建立小堆，父親小于孩子{public:bool operator()(T& x, T& y){return x > y;}};template<class T,class continer=vector<T>,class compre=less<T>>class priority_queue{public:void AdjustUp( size_t child){compre com;int  parent = (child - 1) / 2;while (child>0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void Adjust_Down( size_t parent){compre com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child],_con[child+1])){child++;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}size_t size(){return _con.size();}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}T& top(){return _con[0];}void pop(){int end = _con.size() - 1;swap(_con[0], _con[end]);_con.pop_back();Adjust_Down(0);}private:continer _con;};
}

?由先前的介紹，我們可以知道優(yōu)先隊列存儲數(shù)據(jù)的形式類似于堆，所以，我們在實現(xiàn)優(yōu)先隊列的時候，基本上就是手撕堆，但也不是原搬堆。

首先，我們因為需要存儲多種類型的數(shù)據(jù)，不可能僅僅針對某一個數(shù)據(jù)類型創(chuàng)建單獨的數(shù)據(jù)結(jié)構(gòu)去針對它，所以，我們一般用模板

template<class T,class continer=vector<T>,class compre=less<T>>
class priority_queue

如上所示，貼合stl中的優(yōu)先隊列，我們也給我們的優(yōu)先隊列三個模板參數(shù)，第一個是我們存儲的數(shù)據(jù)類型，第二個是我們的容器，第三個是比較方法，用來切換大堆小堆模式

接口實現(xiàn)

1.push（）

void AdjustUp( size_t child){compre com;int  parent = (child - 1) / 2;while (child>0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}

?當(dāng)我們push進(jìn)一個數(shù)據(jù)元素，它就要與前面已經(jīng)存儲的數(shù)據(jù)元素進(jìn)行排序，找到自己的位置，就和堆一樣，每進(jìn)入一個新數(shù)據(jù)，就要進(jìn)行向上調(diào)整，向上調(diào)整和向下調(diào)整前提都是建立在已經(jīng)是堆的基礎(chǔ)上，但我們這里不需要考慮，因為每次數(shù)據(jù)進(jìn)入前，之前的數(shù)據(jù)已經(jīng)是堆了，第一個數(shù)據(jù)默認(rèn)是堆。

我們這里的向上調(diào)整函數(shù)只用傳一個參數(shù)，原因是我們的成員變量可以被成員函數(shù)隨意訪問，并且我們的成員變量是容器，它本身也可以調(diào)用一些函數(shù)來獲取自身的大小。

2.pop（）

void Adjust_Down( size_t parent){compre com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child],_con[child+1])){child++;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}
void pop(){int end = _con.size() - 1;swap(_con[0], _con[end]);_con.pop_back();Adjust_Down(0);}

?刪除數(shù)據(jù)，同堆一樣，為了最求效率化，將最末尾的數(shù)據(jù)和頭部數(shù)據(jù)進(jìn)行值交換，如何在使堆的大小減一，并采用向下調(diào)整的方式重新排列，使其再次成為新的堆，不過這次的頭部數(shù)據(jù)，是比之前的頭部數(shù)據(jù)小或者大的第二數(shù)據(jù)，向下調(diào)整的基礎(chǔ)是本身是堆，這里符合條件，故可以用向下調(diào)整。

3，top（）

 T& top(){return _con[0];}

很簡單的一段代碼，得益于容器本身的多功能性

4.empty（）

bool empty（）
{return ——con.empty();
}

?仿函數(shù)的介紹

我們之前提到優(yōu)先隊列模板參數(shù)中，需要傳輸比較方法，但模板參數(shù)只能傳輸一個類型，不能傳遞函數(shù)，這里就需要用到仿函數(shù)

所謂的仿函數(shù)，就是模擬函數(shù)，它是利用模板類和重載符合運算符來實現(xiàn)的，具體看代碼

	template<class T>class 類名{返回類型 operator()(參數(shù)列表){函數(shù)體;   }};

這就是一個仿函數(shù)的基本書寫形式，用模板類是使其更加靈活，能夠處理更多的數(shù)據(jù)類型，平常定義的時候，我們需要根據(jù)想要的功能，來書寫函數(shù)體，調(diào)用的時候直接創(chuàng)建一個類對象

類對象（參數(shù)列表）?

這就是仿函數(shù)的調(diào)用形式。

仿函數(shù)的優(yōu)越性在于簡單，與自定義，你可以根據(jù)你的需求去書寫函數(shù)體，用他實現(xiàn)你的功能，然后可以根據(jù)模板參數(shù)選擇要處理的數(shù)據(jù)類型。

注意：我們一般將類名與要實現(xiàn)的功能聯(lián)系起來，這樣可以提高代碼的可讀性。?