前言
之前從沒(méi)用過(guò)優(yōu)先隊(duì)列，刷算法題目的時(shí)候才開始了解的危尿，所以做個(gè)總結(jié)。什么情況下使用呢馁痴？比如當(dāng)你需要獲取到最大最小值元素谊娇，而又不想用最大最小堆的原生實(shí)現(xiàn)，STL提供給你更加簡(jiǎn)單的庫(kù)罗晕，就是priority_queue济欢，其時(shí)間復(fù)雜度也只有o(nlogn)。
說(shuō)明
根據(jù)元素的優(yōu)先級(jí)被讀取小渊，這個(gè)優(yōu)先級(jí)取決于你設(shè)置的排序函數(shù)法褥，如果你沒(méi)設(shè)置，缺省的排序法則則是利用operator<形成降序排列粤铭，也就是從大到小排列的大頂堆挖胃，第一個(gè)自然就是最大的元素。還有如果你沒(méi)設(shè)置保存數(shù)據(jù)的容器Container的話梆惯，默認(rèn)用的是vector酱鸭。
namespace std{
template <class T,
? ? class Container = vector<T>,
? ? class Compare = less<typename Container:: value_type ?>>
????class priority_queue ;
}
priority_queue提供了三個(gè)基本函數(shù)，分別是:
top()
push()
pop()
注意垛吗，pop并不會(huì)返回元素凹髓，top才會(huì)返回堆頂?shù)脑亍?/p>
STL提供了仿函數(shù)greater<>，less<>怯屉，簡(jiǎn)化了自己再定義排序函數(shù)的過(guò)程蔚舀。如果你想使用自己定義的結(jié)構(gòu)，而不想使用基本數(shù)據(jù)類型锨络，也是ok的赌躺，不過(guò)你需要在你自定義的類中重載運(yùn)算符，比如：
class Student{
int id;
char name[20];
bool gender;
bool operator < (Student &a) const{
return id > a.id;? ?
}
};
priority_queue<int, vector<int>, less<int>> maxHeap;//存儲(chǔ)小的值羡儿，值越大礼患，優(yōu)先級(jí)越高
priority_queue<int,vector<int>, greater<int>> minHeap;//存儲(chǔ)大的值，值越小，優(yōu)先級(jí)越高
