優先佇列

本文摘自博客，歡迎前往博客以獲得更好的體驗，

優先佇列

優先佇列可以完成以下操作：

• 插入一個數值
• 取出最小的數值（獲得數值，并且洗掉）

在之前的堆排序，我們已經初步引出了優先佇列的概念，

優先佇列容器與佇列一樣，只能從隊尾插入元素，從隊首洗掉元素，但是它有一個特性，就是佇列中最大的元素總是位于隊首，所以出隊時，并非按照先進先出的原則進行，而是將當前佇列中最大的元素出隊，元素的比較規則默認按元素值由大到小排序，可以多載“<”運算子來重新定義比較規則，

宣告方式

priority_queue <int> q;
priority_queue <double> q;

priority_queue <node> q;
priority_queue<int, vector<int>, cmp>q; 

priority_queue <int,vector<int>,greater<int> > q;
priority_queue <int,vector<int>,less<int> >q;

排序特性

自動排序

在堆排序文章里，我們了解到的是優先佇列的最普通形式，按從大到小排列，

但是，日常的使用時，我們總不可能一直使用從大到小的排列方式吧？那我們應該怎么辦呢？

自定義優先級

無論是C的qsort，還是C++的sort，我們都可以使用cmp函式來自定義排序規則，那么，在優先佇列中，是否也可以使用cmp函式呢？

答案是肯定的，

bool cmp(int a,int b){
    return a < b;
};
priority_queue<int, vector<int>, cmp>q;

less和greater優先佇列

//從大到小
priority_queue <int,vector<int>,less<int> > q;
//從小到大
priority_queue <int,vector<int>,greater<int> > q;

結構體多載

//operator< 多載
struct node{
	  int x,y;
	  bool operator < (const node & a) const{
	    	return x < a.x;
	  }
};//y為值, x為優先級，
priority_queue <node> q;

//operator< 多載
struct node {     
　　int x, y;     
　　bool operator < (node a, node b){         
　　　　return a.x > b.x;    //結構體中，x小的優先級高     
　　}
}; //y為值, x為優先級，
priority_queue<node>q;   //定義方法

例題

在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆，多多決定把所有的果子合成一堆，

每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和，可以看出，所有的果子經過 n ? 1 n-1 n?1 次合并之后， 就只剩下一堆了，多多在合并果子時總共消耗的體力等于每次合并所耗體力之和，

因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節省體力，假定每個果子重量都為 1 1 1 ，并且已知果子的種類 數和每種果子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值，

例如有 3 3 3 種果子，數目依次為 1 1 1 ， 2 2 2 ， 9 9 9 ，可以先將 1 1 1 、 2 2 2 堆合并，新堆數目為 3 3 3 ，耗費體力為 3 3 3 ，接著，將新堆與原先的第三堆合并，又得到新的堆，數目為 12 12 12 ，耗費體力為 12 12 12 ，所以多多總共耗費體力 = 3 + 12 = 15 =3+12=15 =3+12=15 ，可以證明 15 15 15 為最小的體力耗費值，
這是一道典型的優先佇列題目，

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
long long m,n,sum;
priority_queue<int,vector<int>,greater<int> >q;

int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0;i < n;i++) cin >> m,q.push(m);
    for(int i = 1;i < n;i++){
        m = q.top();
        q.pop(),
        m += q.top();
        q.pop();
        sum += m;
        q.push(m);
    }
    cout << sum << "\n";

    return 0;
}