参考链接：https://www.cnblogs.com/xzxl/p/7266404.html

优先队列

能够完成下列操作的数据结构叫做优先队列。

1. 插入一个数值
2. 取出最小的数值(获得数值，并且删除)

能够使用二叉树高效地解决上述问题的，是一种叫做“堆” 的数据结构。

堆的性质，主要是通过堆排序来体现。

Java和c++中都有相应的数据结构，下面介绍c++ STL中的优先队列。

#include<queue>

一，相关定义

优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序，可以重载“<”操作符来重新定义比较规则。

优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue，因为list的迭代器不是任意存取iterator，而pop中用到堆排序时是要求randomaccess iterator 的!)：

priority_queue<vector<int>, less<int> > pq1; 等价于priority_queue<int> q;// 大根堆，默认也是大根堆

priority_queue<int,vector<int>,greater<int> > q2;// 小根堆

其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。

二、priority_queue

基本操作：

empty() 　　   如果队列为空，则返回真

pop()　　　　删除对顶元素，删除第一个元素

push() 　　     加入一个元素

size() 　　　  返回优先队列中拥有的元素个数

top() 　　　　返回优先队列对顶元素，返回优先队列中有最高优先级的元素

在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。

头文件：

#include <queue>

声明方式：

1、普通方法：

priority_queue<int> q;   　　　　　　　　　　　　  //通过操作，按照元素从大到小的顺序出队

priority_queue<int,vector<int>, greater<int> > q;  　　//通过操作，按照元素从小到大的顺序出队

2、自定义优先级：

#include
     
      #include
      
       using namespace std;struct Node{    int x;    int y;}node[5];struct cmp{    bool operator()(const Node &a,const Node &b) { return  a.x > b.x; }};int main(){    priority_queue
       
        
         ,cmp> q1;    node[1].x=1;    node[1].y=2;        node[2].x=-1;    node[2].y=2;        node[3].x=9;    node[3].y=0;        node[4].x=3;    node[4].y=2;        q1.push(node[1]);    q1.push(node[2]);    q1.push(node[3]);    q1.push(node[4]);    while(!q1.empty()){        printf("%3d",q1.top().x);        q1.pop();    }    return 0;}
        
       
      
     

　　

3、结构体声明方式：

struct node {     

　　int x, y;     

　　friend bool operator < (node a, node b)     

　　{         

　　　　return a.x > b.x;    //结构体中，x小的优先级高     

　　}

};

priority_queue<node>q;   //定义方法

//在该结构中，y为值, x为优先级。

//通过自定义operator<操作符来比较元素中的优先级。

//在重载”<”时，最好不要重载”>”，可能会发生编译错误

POJ 2431

题目大意：一辆车从起点出发（装有一定量的油）驶向终点，路上不同位置有加油站，每个加油站都有能加油的上限，问汽车到达终点需要加油次数最少为多少？（若不能到达终点则输出-1）,目前距离终点L个单位，当前拥有P单位油

Sample Input

44 45 211 515 1025 10

Sample Output

2

分析：加油站的数量比较多，逐个比较是不可能的。我们稍微变换一下思考方式。在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站时，就获得了一次在之后的任何时候都可以加B_i单位汽油的权利”，在解决问题上应该也是一样的。而在之后需要加油时，就认为是在之前经过的加油站加的油就可以了。那么，因为希望到达终点时加油次数尽可能少，所以当燃料为0了之后再进行加油看上去是-一个不错的方法。在燃料为0时，应该使用哪个加油站来加油呢?显然，应该选能加油量B_i最大的加油站。 

利用优先队列，经过每个加油站都先把能加的油加入到优先队列当中。等到车没油了，就把优先队列中的最大值弹出（此时相当于加了一次油）。如果优先队列为空，则表示无法到达终点。

注意点：1、本题输入的距离是到终点的距离，应该把距离转化为离起点的距离（这样数据比较好处理）；

              2、输入的距离并不是按顺序的，所以应该排序（用内置的sort）（冒泡会超时）；

              3、将终点也看成一个加油站，处理起来比较方便；

c++版本解法

#include
     
      #include
      
       #include
       
        #define M  10005using namespace std;struct gas{    int dis;//注意这里的距离是距终点的距离    int fule;};bool cmp(gas A, gas B){    return A.dis < B.dis;}gas a[M];priority_queue
        
          que;int N, L, P;int main(){    scanf("%d", &N);    for(int i = 0; i < N; i++)        scanf("%d %d", &a[i].dis, &a[i].fule);    scanf("%d %d", &L, &P);    for(int i = 0; i < N; i++)        a[i].dis = L - a[i].dis;    //把加油站按照距离起点距离从小到大排序    sort(a, a + N, cmp);    //把终点也看成一个加油站    a[N].dis = L;    a[N].fule = 0;    N++;//绝对不能少，加一个油站    //count:加油次数，position:现在所在位置，tank：油箱中的油量    int count = 0, position = 0, tank = P;    for(int i = 0; i < N; i++)    {        //经过每个加油站要前进的距离        int d = a[i].dis - position;        //不断加油直到可以行驶到下一个加油站        while(tank - d < 0)        {            if(que.empty())            {                puts("-1");                return 0;            }            tank = tank + que.top();            que.pop();            count++;        }        //行驶到了该油站，把该油站的油放入优先队列中        tank = tank - d;        position = a[i].dis;        que.push(a[i].fule);    }    printf("%d\n", count);    return 0;}
        
       
      
     

Java版本解法：

package 优先队列;import java.util.Arrays;import java.util.Comparator;import java.util.PriorityQueue;import java.util.Scanner;public class Main {	static class Gas implements Comparable
     
      {		int dis;		int fule;		public Gas(int dis, int fule) {			this.dis = dis;			this.fule = fule;		}		@Override		public int compareTo(Gas o) {						return this.dis>o.dis?1:-1;		}			}	public static void main(String[] args) {		Scanner sc=new Scanner(System.in);		int N=sc.nextInt();		Gas arr[]=new Gas[N+1];		for (int i = 0; i < N; i++) {			int dis=sc.nextInt();			int fule=sc.nextInt();			Gas gas=new Gas(dis, fule);			arr[i]=gas;		}		int L=sc.nextInt();		int P=sc.nextInt();		for(int i = 0; i < N; i++)	        arr[i].dis = L - arr[i].dis;		arr[N]=new Gas(L, 0);		Arrays.sort(arr);		//count:加油次数，position:现在所在位置，tank：油箱中的油量	    int count = 0, position = 0, tank = P;	    //java中默认创建的是小根堆，所以要改成大根堆	    PriorityQueue
      
        que= new PriorityQueue<>(N+1, new Comparator
       
        () {			@Override				public int compare(Integer o1, Integer o2) {                		            return o2-o1;		        }		});	    for(int i = 0; i < N+1; i++)	    {	        //经过每个加油站要前进的距离	        int d = arr[i].dis - position;	        //不断加油直到可以行驶到下一个加油站	        while(tank - d < 0)	        {	            if(que.isEmpty())	            {	               throw new RuntimeException("-1");	            }	            tank = tank + que.poll();	            count++;	        }	        //行驶到了该油站，把该油站的油放入优先队列中	        tank = tank - d;	        position = arr[i].dis;	        que.add(arr[i].fule);	    }		System.out.println(count);	}}　
       
      
     

---

　

Fence Repair ( POJ 3253)

农夫约翰为了修理栅栏，要将一块很长的木板切割成N块。准备切成的木板的长度为L、L2、... LN,未切割前木板的长度恰好为切割后木板长度的总和。每次切断木板时，需要的开销为这块木板的长度。例如长度为21的木板要切成长度为5、8、8的三块木板。长21的木板切成长为13和8的板时，开销为21。再将长度为13的板切成长度为5和8的板时，开销是13。于是合计开销是34。请求出按照目标要求将木板切割完最小的开销是多少。

Input

Line 1: One integer 

N, the number of planks 

Lines 2..

N+1: Each line contains a single integer describing the length of a needed plank

Output

Line 1: One integer: the minimum amount of money he must spend to make 

N-1 cuts

Sample Input

3858

Sample Output

34

---

解析：由于只需从板的集合里取出最短的两块,并且把长度为两块板长度之和的板加入集合中即可，因此如果使用优先队列就可以高效地实现。一共需要进行O(N)次O(og N)的操作，因此总的时间复杂度是O(N log N)。 这种方法使用优先队列实现了哈夫曼树裸题，用优先队列做的。

 

#include 
      
       #include 
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;#define MAX_N 10000int N,L[MAX_N];void solve() {    ll ans=0;    //声明一个从小到大取出数值的优先队列    priority_queue
          
           
            ,greater
            
             > que; for(int i=0;i
             
               1) { //取出最短的木板和次短的木板int 11，12 ; int l1 = que.top(); que.pop() ; int l2 = que.top(); que.pop() ; //把两块木板合并 ans+=l1+l2; que. push(l1 + l2) ; } printf ( "%lld\n", ans) ;}int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> L[i]; } solve(); return 0;}
             
            
           
          
         
        
       
      

JAVA解法

package 优先队列;import java.util.PriorityQueue;import java.util.Scanner;public class Main1 {	static int N;	static int[] L;	public static void main(String[] args) {		Scanner sc=new Scanner(System.in);		N=sc.nextInt();		L=new int[N];		for (int i = 0; i < N; i++) {			L[i]=sc.nextInt();		}		solve();	}	private static void solve() {		long ans=0;		PriorityQueue
      
        que=new PriorityQueue<>();//默认小根堆		for (int i = 0; i < N; i++) {			que.add(L[i]);		}		 while (que.size() > 1) {		        //取出最短的木板和次短的木板int 11，12 ;		        int l1 = que.poll();		 		        int l2 = que.poll();		        //把两块木板合并		        ans+=l1+l2;		        que.add(l1 + l2) ;		    }		 		    System.out.printf( "%d\n", ans) ;	}}