前言

本篇主要講解優先隊列及其底層實現。

優先隊列

優先隊列的本質就是個堆，其與queue一樣，都是容器適配器，不過優先隊列是默認為vector實現的。priority_queue的接口優先隊列默認為大根堆。

仿函數

我們觀看文檔可以發現

優先隊列是有三個參數的，第二個參數即默認用vector進行實現優先隊列，第三個參數即默認為大堆，less是已經實現了的仿函數，這里注意的是大堆是傳的less，小堆傳的是greater，是反著的。
仿函數實際是一個類，類中重載了()這個運算符，仿函數的實現能讓我們自己定義來比較的標準，而不是用默認的。例如將默認為大堆更改為小堆，將sort默認為升序改為降序。

template<class T>
class less
{bool operator()(const T& a1, const T& a2){return a1 < a2;}
};

頭文件

#include<iostream>
#include<vector>
#include<algorithm>
namespace prime
{//這是仿函數，仿函數是一個類template<class T>class less{public:bool operator()(const T& a1, const T& a2){return a1 < a2;}};template<class T>class greater{public:bool operator()(const T& a1, const T& a2){return a1 > a2;}};template<class T>class less<T*>//特化{public:bool operator()(const T* const & x, const T* const & y){return *x < *y;}};template<class T,class container = vector<T>,class cmp = less<T>>class priority_queue{public:priority_queue(){}void push_back(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}const T& top(){return _con[0];}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:void adjustup(int child){cmp com;//需要先實例化出一個com對象while (child > 0){int parent = (child - 1) / 2;//if (_con[parent] < _con[child])//if(com(_con[parent],_con[child]))if(cmp()(_con[parent],_con[child]))//匿名對象{swap(_con[child], _con[parent]);child = parent;}elsebreak;}}void adjustdown(int parent){cmp com;int child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child],_con[child + 1])){child++;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}private:container _con;};
}