STL应用 —— priority_queue

STL应用 —— priority_queue

priority_queue是一个优先队列，优先级高的最先出队，默认最大值优先。内部实现为堆，因此出队和入队的时间复杂度均为O (logn)。可以自定义优先级控制出队顺序，如果是数值，则也可以采用加负号的方式实现最小值优先，优先队列不支持删除堆中的指定元素，只可以删除堆顶元素，如果需要删除指定元素，则可以采用懒操作。使用priority_queue时，需要引入头文件#include 。

【优先队列的成员函数】

• push(x)：x 入队。
• pop()：出队。
• top()：取队头。
• size()：返回队中的元素个数。
• empty()：判断队空，若为空则返回true。

【举个栗子】

POJ No.1442 黑盒子

官方题目地址

题意

黑盒子代表一个原始数据库，保存一个整数数组和一个特殊的i 变量。在最初的时刻，黑盒子是空的，i =0。黑盒子处理一系列命令（事务），有以下两种类型的事务。

• ADD(x)：将元素x 放入黑盒子。
• GET：将i增加1，并给出包含在黑盒子中的所有整数中第i小的值。第i小的值是黑盒子中按非降序排序后的第i个位置的数字。

示例

写一个有效的算法来处理给定的事务序列。

ADD和GET事务的最大数量均为30000。使用两个整数数组来描述事务的顺序。

【输入输出】

（1）A(1),A(2),…,A(M)：包含在黑盒子中的一系列元素。A值是绝对值不超过2 000 000 000的整数，M ≤30 000。对于示例，序列A =(3, 1, -4, 2, 8, -1000, 2)。

（2）u (1),u (2),…,u (N )：表示在第1个,第2个,…,第N个GET事务时包含在黑盒子中的元素个数。对于示例，u =(1, 2, 6, 6）。

假设自然数序列u (1),u (2),…,u (N)按非降序排序，N ≤M 且每个p （1≤p ≤N ）对不等式p ≤u (p )≤M 都有效。由此得出这样的事实：对于u 序列的第p 个元素，执行GET事务，给出A(1),A(2),…,A(u (p ))序列第p 小的数。

输入：

输入包含M ,N ,A(1) ,A(2) ,…,A(M ) ,u (1) ,u (2) ,…,u (N )。

输出：

根据给定的事务顺序输出答案序列，每行一个数字。

【样例】

【算法设计】

采用两个优先队列：一个是最大值优先队列q1 ，保存前i -1大的数；另一个是最小值优先队列q 2 ，保存从i 到序列末尾的数。q2的堆顶就是要查询的第i 小的数。

1. 使用cnt计数，控制放入黑盒子的元素个数
2. 读入u(i)，如果cnt <= u(i)，则重复以下操作：如果q1不空且a[cnt] < q1.top()，则说明a [cnt]属于前i - 1大的数，因此将q1 堆顶放入q2 ， q1堆顶出队，将 a[cnt]放入q1 ；否则直接将a [cnt]放入q2。cnt ++
3. 输出q2 的堆顶(第 i 小的数)
4. 因为查询第 i 小时，i 都增加1，所以每次处理完毕后，都需要将q2中的堆顶放入q1 ， q2 堆顶出队。

【算法实现】

#include
#include

using namespace std;

priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
int a[30010];

int main(){
	
    int n,m,x;
    scanf("%d%d",&m,&n);
    
    for(int i=1;i<=m;i++){
    	scanf("%d",&a[i]);
	}	
    int cnt=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        while(cnt<=x){
            if(!q1.empty()&&a[cnt]<q1.top()){
            	q2.push(q1.top());
            	q1.pop();
            	q1.push(a[cnt]);
			}
			else{
				q2.push(a[cnt]);	
			}
            cnt++;
        }
        printf("%d\n",q2.top());
        q1.push(q2.top());
		q2.pop();
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38