網(wǎng)站列表頁內(nèi)容優(yōu)化關(guān)鍵詞哪家好
優(yōu)先隊列(priority_queue)
? ?優(yōu)先隊列是一種特殊的隊列,它同一般隊列一樣,都支持先入先出的規(guī)則,但不同于一般隊列的是,它對存儲的數(shù)據(jù)有著自己獨特的存儲風格。
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ù)
- T為存儲的數(shù)據(jù)類型
- Container為容器,如list,vector等,決定了優(yōu)先隊列中數(shù)據(jù)的存儲方式
- Compare為比較方法,?它對存儲的數(shù)據(jù)進行排序提供比較方法
優(yōu)先隊列的模板參數(shù)中,除了第一個數(shù)據(jù)類型沒有缺省值,其他兩個均有缺省值,也代表在實際使用中,我們不顯示寫出后兩個模板參數(shù)也可以。?
優(yōu)先隊列會對每一個存進的數(shù)據(jù)進行排序,這類似于我們之前學習的一個數(shù)據(jù)結(jié)構(gòu),也就是堆,它會對新加入的數(shù)據(jù)元素進行向上調(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)粘5恼J知相違背,我們記住就好,c++就是這么定義的(less和greater是c++中的兩個比較函數(shù))
?優(yōu)先隊列的接口
- ?top()取出隊頭元素
- pop()刪除隊頭元素
- push()添加隊元素,并按照一定比較方法,與前面的數(shù)據(jù)比較,找到自己的新位置
- 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);}
?當我們push進一個數(shù)據(jù)元素,它就要與前面已經(jīng)存儲的數(shù)據(jù)元素進行排序,找到自己的位置,就和堆一樣,每進入一個新數(shù)據(jù),就要進行向上調(diào)整,向上調(diào)整和向下調(diào)整前提都是建立在已經(jīng)是堆的基礎(chǔ)上,但我們這里不需要考慮,因為每次數(shù)據(jù)進入前,之前的數(shù)據(jù)已經(jīng)是堆了,第一個數(shù)據(jù)默認是堆。
我們這里的向上調(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ù)進行值交換,如何在使堆的大小減一,并采用向下調(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)系起來,這樣可以提高代碼的可讀性。?