STL详解（四） 优先对列容器priority queue_priority_queueq;

一、优先队列priority_queue简介

        priority_queue（优先队列）允许用户为队列中元素设置优先级，放置元素的时候不是直接放到队尾，而是放置到比它优先级低的元素前面。

priority_queue有三个模板参数：priority_queue<Type, 　Container, 　Functional>，其中后两个可以省略。

Type :为数据类型，

Container: 为保存数据的容器，必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector。

Functional :为元素比较方式。基本数据类型或已定义了比较运算符的类，可以直接用STL的less算子和greater算子——默认使用less算子，即小的往后排，大的往前排，大的先出队（出队时，序列顶的最大的元素出队）。

对于greater 算子大的往后排，小的往前排，小的先出队（出队时，序列顶的最小的元素出队）。

二、定义priority_queue对象

示例代码如下：

priority_queue<int> q1;

priority_queue<pair<int,int>> q2;

priority_queue<int,vector<int>,greater<int>> q3;//定义优先级小的先出队
 

三、成员函数列表及详细说明：

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

pop() 删除队顶元素

push() 加入一个元素

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

top() 返回优先队列队顶元素（队列中的front()变成了top()）

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

注意：priority queue和 queue不同的是，priority queue没有j back() 和 front() ，而只能通过top()或pop()  ,访问队尾元素（也称堆顶元素），也就是优先级最高的元素。

1、int 类型比较（默认从大到小，大的先出）

#include <bits/stdc++.h>
using namespace std;
int main ()
{	priority_queue<int> q;
	q.push(1);
	q.push(5);
	q.push(3);
	q.push(9);
	q.push(2);
	cout<<q.top()<<endl;
	q.pop();
	cout<<q.top()<<endl;
	system("pause");
	return 0;
}

结果为：

改写算子（从小到大，小的先出）

#include <bits/stdc++.h>
using namespace std;
int main ()
{	priority_queue<int,vector<int>,greater<int> > q;
	q.push(1);
	q.push(5);
	q.push(3);
	q.push(9);
	q.push(2);
	cout<<q.top()<<endl;
	q.pop();
	cout<<q.top()<<endl;
	system("pause");
	return 0;
}

结果为：

2.pari的比较，先比较第一个元素，第一个相等比较第二个

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}

使用priority_queue时，最困难的可能就是如何定义比较算子了。

四、自己定义比较算子

    可以有多种方法，最常见的就是重载比较运算符，注意重载操作返回的结果是bool类型，并且此处的比较操作与map等其他处不同，在map中以<作为比较操作，则值小的排在前面，而优先级队列中以<作为比较操作，值大的优先级高，而优先级高的放在队列前面，反之以>操作符确定优先级关系时，表明优先级是按值从大到小排列，值小的优先级高，优先级高的放在队列前面。

自定义优先级的三种方法：

1.结构体声明方式：定义在结构体内部

第一种方式：

struct node{
    int value;
    friend bool operator<(const node &a,const node &b){
        return a.value<b.value;  //按value从大到小排列
    }
};
priority_queue<node>q;  

第二种方式：

struct T{
    int x,y,z;
    bool operator<(const T &a) const {
        return z<a.z; // '>'按照z从小到大排列,'<'按照z从大到小排列
    }
}a;

        下面这个例子是结构体声明方式，在priority_queue中插入若干个结构体，结构体成员为(x,y,z)，以结构体成员z值来确定优先级顺序：

#include <bits/stdc++.h>
using namespace std;
struct T{
    int x,y,z;
    friend bool operator<(const T &a,const T &b){
        return a.z<b.z; // '>'按照z从小到大排列,'<'按照z从大到小排列
    }
}a;
priority_queue<T>q;  
 
int main()  
{   for(int i=1;i<=4;i++)
    {  cin>>a.x>>a.y>>a.z;
       q.push(a);
	}   
    
    while(!q.empty())  
    {   T t=q.top();  
        q.pop();  
        cout<<t.x<<" "<<t.y<<" "<<t.z<<endl;  
    }  
    system("Pause");  
    return 1;  
}  

　

#include <bits/stdc++.h>
using namespace std;
struct T{
    int x,y,z;
    bool operator<(const T &a) const {
        return z<a.z; // '>'按照z从小到大排列,'<'按照z从大到小排列
    }
}a;
priority_queue<T>q;  
 
int main()  
{   for(int i=1;i<=4;i++)
    {  cin>>a.x>>a.y>>a.z;
       q.push(a);
	}   
    
    while(!q.empty())  
    {   T t=q.top();  
        q.pop();  
        cout<<t.x<<" "<<t.y<<" "<<t.z<<endl;  
    }  
    system("Pause");  
    return 1;  
}  

　

输入：

4 4 3 2 2 5 1 5 4 3 3 6

输出：

2、结构体声明方式：定义在结构体外部，重载操作符:

bool operator < (const node &a, const node &b) //或者写成 bool operator<( const node &a, const node &b)  
 {
     return a.value < b.value; // 按照value从大到小排列
 } 
priority_queue<node>q;

(const node &a是用引用传递，比按值传递node a效率更高，效果是一样的).

　　下面这个例子是重载比较运算符，在priority_queue中插入若干个结构体，结构体成员为(x,y,z)，以结构体成员z值来确定优先级顺序，z值大的排在队列前面：

#include <bits/stdc++.h>
using namespace std;
struct T  
{  int x,y,z;   
}a;  
bool operator<(const T &t1,const T &t2)  //或者写成 bool operator<( const T &t1, const T &t2)  
{     return t1.z<t2.z;  // '>'按照z从小到大排列,'<'按照z从大到小排列
}  
int main()  
{   priority_queue<T>q; 
    for(int i=1;i<=4;i++)
    {  cin>>a.x>>a.y>>a.z;
       q.push(a);
	}   
    
    while(!q.empty())  
    {   T t=q.top();  
        q.pop();  
        cout<<t.x<<" "<<t.y<<" "<<t.z<<endl;  
    }  
    system("Pause");  
    return 1;  
}  

输入：

4 4 3 2 2 5 1 5 4 3 3 6

输出：

3.比较函数声明方式:

struct cmp{
 
    bool operator ()( node &a, node &b)//或者写成 bool operator<(const node &a, const node )  
    {
        return a.value>b.value;// 按照value从小到大排列
    }
};
priority_queue<node, vector<node>, cmp>q;

下面这个例子是自定义比较函数，在priority_queue中插入若干个结构体，结构体成员为(x,y,z)，以结构体成员z值来确定优先级顺序：

#include <bits/stdc++.h>
using namespace std;
struct T  
{  int x,y,z;   
}a;  
struct cmp
{   bool operator ()(T &a, T &b)  //或者写成 bool operator ()(const T &a,const T &b)
    {  return a.z>b.z;// '>'按照z从小到大排列,'<'按照z从大到小排列
    }
};
priority_queue<T, vector<T>, cmp>q;
 
int main()  
{   for(int i=1;i<=4;i++)
    {  cin>>a.x>>a.y>>a.z;
       q.push(a);
	}   
    
    while(!q.empty())  
    {   T t=q.top();  
        q.pop();  
        cout<<t.x<<" "<<t.y<<" "<<t.z<<endl;  
    }  
    system("Pause");  
    return 1;  
}  

输入：

4 4 3 2 2 5 1 5 4 3 3 6

输出：

 

五　应用举例：

1、P3887 [GDOI2014] 世界杯

１、  有序表的最小和

【问题描述】

给出两个长度为 n 的有序表 A 和 B，在 A 和 B 中各任取一个元素，可以得到 n 2 个和，求这些和中最小的 n 个。

【输入格式】

第 1 行包含 1 个整数正 n（n≤400000）。

第 2 行与第 3 行分别有 n 个整数，各代表有序表 A 和 B。一行中的每两个整数之间用一个空格隔开，大小在长整型范围内，数据保证有序表单调递增。

【输出格式】

输出共 n 行，每行一个整数，第 i 行为第 i 小的和。

数据保证在 long long 范围内。  

【输入样例】

3

1 2 5

2 4 7

【输出样例】

3

4

5

２、合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3种果子，数目依次为 1， 2， 9。可以先将 1 、 2堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 3+12=15 。可以证明 15 为最小的体力耗费值。

输入输出格式

输入格式：

共两行。
第一行是一个整数 n(1≤n≤10000) ，表示果子的种类数。

第二行包含 n 个整数，用空格分隔，第 i 个整数ai​(1≤ai​≤20000) 是第 i 种果子的数目。

输出格式：

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2^31 。

输入输出样例

输入样例#1： 

3 
1 2 9 

输出样例#1： 

15

说明

对于30％的数据，保证有n≤1000：

对于50％的数据，保证有n≤5000；

对于全部的数据，保证有n≤10000

3、priority queue练习

总时间限制: 2500ms　　　内存限制: 131072kB

描述

我们定义一个正整数a比正整数b优先的含义是：
*a的质因数数目（不包括自身）比b的质因数数目多；
*当两者质因数数目相等时，数值较大者优先级高。

现在给定一个容器，初始元素数目为0，之后每次往里面添加10个元素，每次添加之后，要求输出优先级最高与最低的元素，并把该两元素从容器中删除。

输入

第一行: num (添加元素次数，num <= 30)

下面10*num行，每行一个正整数n（n < 10000000).

输出

每次输入10个整数后，输出容器中优先级最高与最低的元素，两者用空格间隔。

样例输入

1
10 7 66 4 5 30 91 100 8 9

样例输出

66 5

4、看病要排队

看病要排队这个是地球人都知道的常识。 
不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。 

现在就请你帮助医院模拟这个看病过程。

Input

输入数据包含多组测试，请处理到文件结束。 
每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。 
接下来有N行分别表示发生的事件。 
一共有两种事件： 
1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)
2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)

Output

对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治，则输出"EMPTY"。 
诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。 

Sample Input

7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1

Sample Output

2
EMPTY
3
1

思路：简单的模拟，或者直接用优先队列，因为病人的级别越高就有更高的优先权，所以用优先队列更容易理解；

代码:模拟

#include<bits/stdc++.h>
using namespace std;
int n,k;
int s1[2010],s2[2010],s3[2010],s[2010];
void fun(int a) {
	int i,t=0,max=-1;
	if(a==1) {
		for(i=1; i<k; i++)
			if(s1[i]&&s1[i]>max) { //判断A级医生诊断的病人且级别高的人优先看病
				max=s1[i];
				t=i;
			}
		s1[t]=0;
		s[n++]=t;// 把病人的ID储存起来
	} else if(a==2) { //B级医生与A医生级相同 ，同理A级医生
		for(i=0; i<k; i++)
			if(s2[i]&&s2[i]>max) {
				max=s2[i];
				t=i;
			}
		s2[t]=0;
		s[n++]=t;
	} else {
		//同理与上
		for(i=0; i<k; i++)
			if(s3[i]&&s3[i]>max) {
				max=s3[i];
				t=i;
			}
		s3[t]=0;
		s[n++]=t;
	}
}
int main() {
	int m;
	while(~scanf("%d",&m)) {
		int i,j,a,b;
		n=0;
		k=1;
		memset(s1,0,sizeof(s1));//清空数组；
		memset(s2,0,sizeof(s2));
		memset(s3,0,sizeof(s3));
		char c[100];
		for(i=0; i<m; i++) {
			scanf("%s",c);
			if(c[0]=='I') {
				scanf("%d%d",&a,&b);
				if(a==1)//把看病的病人储存在数组中
					s1[k++]=b;//不同医生看的病人储存在不同的数组中
				else if(a==2) s2[k++]=b;
				else     s3[k++]=b;
			}
			if(c[0]=='O') { //当有 医生诊治完时，
				scanf("%d",&a);
				fun(a);//储存医生诊断的病人；
			}
		}
		for(i=0; i<n; i++) {
			if(s[i])//如果数组s不为0，说明有医生诊断 ，否则就没有；
				printf("%d\n",s[i]);
			else
				printf("EMPTY\n");
		}
	}
}

思路：将每个病人的信息储存为一个结构体，将每个医生的求诊信息当成队列数组中的元素。以病人的级别，若级别相同，则以病人来到医院的先后作为队列的优先级。

代码：优先队列

#include<bits/stdc++.h>
using namespace std;
struct per {
	int num,id;
} s;
//先定义结构体，再写重载函数定义优先级比较简单明了
bool operator < (const per &x,const per &y) { //重载 "<" 操作符定义优先级
	if(x.num==y.num)//当级别相同时从小到大排序
		return x.id>y.id;
	else
		return x.num<y.num;//当级别不同是从大到小排序
}
 
int main() {
	int n,a,b;
	char str[5];
	while(scanf("%d",&n)!=EOF) {
		int k=1;
		priority_queue<per>q[4];
		while(n--) {
			scanf("%s%d",str,&a);
			if(strcmp(str,"IN")==0) {
				scanf("%d",&b);
				s.num=b;
				s.id=k++;//储存病人的ID;
				q[a].push(s);//把病人入队列；
			} else {
				if(!q[a].empty()) { //有医生诊断
					s=q[a].top();
					q[a].pop();
					printf("%d\n",s.id);
				} else
					printf("EMPTY\n");
			}
		}
	}
	return 0;
}

１、  有序表的最小和

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>,greater<int> > q;
int n,i,j,a[400001],b[400001];
int main()  
{   
    cin>>n;
    for( i=1;i<=n;i++)  cin>>a[i]; 
    for(i=1;i<=n;i++)   cin>>b[i];  
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)  
         q.push(a[i]+b[j]);
    
    for(i=1;i<=n;i++)
    {    cout<<q.top()<<endl;  q.pop();   }      
}