priority_queue介紹

pri_que是一個容器適配器，它的底層是其他容器，并由這些容器再封裝而來。類似于heap的結構。默認為大堆。

邏輯實現

框架

namespace xty 
{template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con.front();}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}private:Container _con;};
}

調整算法

因為優先級隊列是以堆為結構實現的，因此插入刪除要保持堆的結構，需要adjust_up()和adjust_down()兩個算法。
建堆算法詳細參考

adjust_up()

向上調整，由堆底一直調整到堆頂。

		void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

adjust_down()

向下調整，由堆頂一直向下調整直到葉子。

		void adjust_down(int parent){size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){child++;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}

仿函數/比較函數

我們觀察到庫的模板參數給了三個，其中第一個參數是數據類型，第二個參數是模板容器，第三個參數就是仿函數（用戶可以自己制定比較規則！），默認為大堆less。

template<class T, class Container = vector<T>, class Compare = less<T>>

接下來我們實現一個比較類：

	template<class T>struct less{bool operator() (const T& x, const T& y){return x > y;}};template<class T>struct grater{bool operator() (const T& x, const T& y){return x < y;}};

然后我們微調調整函數的邏輯將if的內容改成比較函數：
因為使用方法酷似函數，因此它叫仿函數 ！

		void adjust_up(int child){Compare com;  //實例化比較函數int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent]))/*if (_con[child] > _con[parent])*/{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;  //實例化比較函數size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1], _con[child])){child++;}if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}

仿函數特性

有了仿函數的功能后，我們可以自己定義比較類型，使程序設計更加靈活。

看下面一段代碼：

	class Date{public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;};void test_priority_queue2(){// 大堆，需要用戶在自定義類型中提供<<的重載//priority_queue<Date> q1;priority_queue<Date, vector<Date>, greater<Date>> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 30));q1.push(Date(2018, 10, 28));cout << q1.top() << endl;}

首先這段測試代碼結果是唯一的：

而如果我們增加另一種格式的代碼呢？

	class PDateLess{public:bool operator()(const Date* p1, const Date* p2){return *p1 < *p2;}};class PDateGreater{public:bool operator()(const Date* p1, const Date* p2){return *p1 > *p2;}};void test_priority_queue2(){//priority_queue<Date*, vector<Date*>, PDateLess> q2;priority_queue<Date*, vector<Date*>, PDateGreater> q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 30));q2.push(new Date(2018, 10, 28));cout << *(q2.top()) << endl;}

這段代碼如果不寫仿函數，結果是不唯一的，因為比較的是指針，重寫仿函數后，答案就唯一了！！可以看見，仿函數可以使我們比較數據更加靈活！

構造函數

顯然我們沒有寫構造函數，程序并沒有報錯，是因為：

• 我們不寫構造函數，編譯器會默認生成一個。而成員函數是自定義類型，會調用自定義類型的構造函數，所以程序沒有問題運行。
• 當我們寫了構造函數之后，編譯器就不會再默認生成了，需要我們自己寫。

迭代器區間構造

因為自己顯示寫了構造函數，編譯器不再默認生成默認構造函數，需要自己再顯示補一個默認構造！

		//默認構造priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){Container _con;while (first!= last){push(*first);first++;}}

完整優先級隊列代碼

namespace xty 
{template<class T>struct less{bool operator() (const T& x, const T& y){return x > y;}};template<class T>struct grater{bool operator() (const T& x, const T& y){return x < y;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void adjust_up(int child){Compare com;  //實例化比較函數int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent]))/*if (_con[child] > _con[parent])*/{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;  //實例化比較函數size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1], _con[child])){child++;}if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con.front();}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){Container _con;while (first!= last){push(*first);first++;}}private:Container _con;};
}