部落格轉載自：https://www.cnblogs.com/George1994/p/6477198.html
前言
之前從沒用過優先隊列，刷算法題目的時候才開始了解的，是以做個總結。什麼情況下使用呢？比如當你需要擷取到最大最小值元素，而又不想用最大最小堆的原生實作，STL提供給你更加簡單的庫，就是priority_queue，其時間複雜度也隻有o(nlogn)。
說明
根據元素的優先級被讀取，這個優先級取決于你設定的排序函數，如果你沒設定，預設的排序法則則是利用operator<形成降序排列，也就是從大到小排列的大頂堆，第一個自然就是最大的元素。還有如果你沒設定儲存資料的容器Container的話，預設用的是vector。
namespace std {
template < class T ,
class Container = vector<T> ,
class Compare = less <typename Container::value_type> >
class priority_queue ;
}
priority_queue提供了三個基本函數，分别是:
- top()
- push()
- pop()
注意，pop并不會傳回元素，top才會傳回堆頂的元素。
STL提供了仿函數greater<>，less<>，簡化了自己再定義排序函數的過程。如果你想使用自己定義的結構，而不想使用基本資料類型，也是ok的，不過你需要在你自定義的類中重載運算符，比如：
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; //存儲小的值，值越大，優先級越高
priority_queue<int, vector<int>, greater<int>> minHeap; //存儲大的值，值越小，優先級越高
/**
* 完全不需要判斷各種判斷
* 不過一定要注意minHeap和maxHeap的優先級順序，避免弄反了
*/
void addNum3(int num) {
minHeap.push(num);
maxHeap.push(minHeap.top());
minHeap.pop();
// 平衡
if (minHeap.size() < maxHeap.size()) {
minHeap.push(maxHeap.top());
maxHeap.pop();
}
}
double findMedian3() {
return maxHeap.size() == minHeap.size() ? (double)(maxHeap.top() + minHeap.top())/2.0 : (double)minHeap.top()/1.0;
}
void test() {
this->addNum3(1);
this->addNum3(2);
cout << this->findMedian3() << endl;
this->addNum2(3);
cout << this->findMedian3() << endl;
}
輸出結果
1.5
2 底層實作
顯然，我們可以看出priority_queue的底層實作是堆實作的。裡面的c就是你自己提供的容器Container
void push(value_type&& _Val)
{ // insert element at beginning
c.push_back(_STD move(_Val));
push_heap(c.begin(), c.end(), comp);
}
template<class... _Valty>
void emplace(_Valty&&... _Val)
{ // insert element at beginning
c.emplace_back(_STD forward<_Valty>(_Val)...);
push_heap(c.begin(), c.end(), comp);
}
bool empty() const
{ // test if queue is empty
return (c.empty());
}
size_type size() const
{ // return length of queue
return (c.size());
}
const_reference top() const
{ // return highest-priority element
return (c.front());
}
void push(const value_type& _Val)
{ // insert value in priority order
c.push_back(_Val);
push_heap(c.begin(), c.end(), comp);
}
void pop()
{ // erase highest-priority element
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
實際使用中将節點存在優先隊列中的兩種方式
struct Node
{
int x,y;
bool operator <(Node a) const { return y < a.y; }
bool operator >(Node a) const { return y > a.y; }
};
priority_queue<Node> A; //大根堆
priority_queue<Node, vector<Node>, greater<Node> > B; //小根堆 方式一
struct Node
{int adj;
int val;
friend bool operator<(const Node &a,const Node &b) { return a.val > b.val; }
};
priority_queue<Node>Q;
方式二：（cmp将結構體以val由大到小排列，組成大根堆）一般也用這個！
struct Node
{int adj;
int val;
};
struct cmp
{bool operator()(Node a,Node b) { return a.val > b.val; }
};
priority_queue<Node,vector<Node>,cmp>Q;
方式三
struct TMax
{
TMax(int tx):x(tx){}
int x;
};
struct TMin
{
TMin(int tx):x(tx){}
int x;
};
bool operator<(const TMax &a, const TMax &b)
{
return a.x<b.x;
}
bool operator<(const TMin &a, const TMin &b)
{
return a.x>b.x;
}
priority_queue<TMax> hmax; //大頂堆
priority_queue<TMin> hmin; //小頂堆
3.下面是将指針存在優先隊列中的方式
struct Node
{
short f;
short d;
short fishs;
short times;
short i;
};
struct PCmp
{
bool operator () (Node const *x, Node const *y)
{
if(x->f == y->f)
return x->i > y->i;
return x->f < y->f;
}
};
priority_queue<Node*, vector<Node*>, PCmp > Q; 注：在這種情況下往往可以預配置設定空間以避免new帶來的麻煩。例如：堆中定義Node Qt[26]， 棧中的使用則為Node *tmp1 = Qt。經過測試，在優選隊列當中存指針進行一系列操作要比存節點進行一系列操作快一些。
注：
- less<class T>這是大頂堆，按值大的優先，值大的在最上面。greater<class T>這是小頂堆，按值小的優先，值小的在最上面。
- 自定義cmp如果還有不明白的看這裡
struct cmp { bool operator()（const int &a,const int &b）//這裡的&是引用 { return a>b;//最大堆 return a<b;//最小堆 } }; priority_queue< int, vector<int>, cmp > - 還是自定義cmp函數，注意，一般ACM中用結構體内含“bool operator()（const int &a,const int &b）”。這其實等價于Class cmp，不過更省事，當然也不規範（不需要規範）。
- return就是希望如何排列為true。如果希望由大到小，就将大到小的情況return；反則亦然。和sort的自定義cmp是一樣的。