原文：https://blog.csdn.net/u012804490/article/details/26241523
优先队列
优先队列(priority queue)亦即数据结构中的堆，是计算机科学中一类特殊的数据结构的统称。在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待长时间才能结束，或某些不短小，但具有重要性的作业，同样应当具有优先权。优先队列即为解决此类问题设计的一种数据结构。优先队列(堆)通常是一个可以被看做一棵树的数组对象。
优先队列中的常用函数：
empty() 如果优先队列为空，返回真
pop() 删除第一个元素
push(x) 添加一个元素x
size() 返回优先队列中拥有的元素的个数
top() 返回优先队列中有最高优先级的元素
例如：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int i;
priority_queue<int> q;
// 向队列中添加元素
q.push(4); q.push(1);
q.push(3); q.push(5);
q.push(6); q.push(2);
int len=q.size(); // 统计优先队列中元素的个数
for(i=0;i<len;i++)
{
// top()返回优先级最高的元素
// 在优先队列中，默认为大根堆，即默认元素大的优先级高
printf("%d ",q.top());
q.pop(); // 删除第一个元素，也即优先级最高的元素
}
printf("\n");
if(q.empty()) // 此时该优先队列中元素已删除完
printf("该优先队列为空\n");
return 0;
}
输出结果为：
6 5 4 3 2 1
该优先队列为空
如果我们希望在优先队列中的较小的元素优先出队，该怎么做呢？
So easy！
我们只需将priority_queue<int> q;改为priority_queue<int,vector<int>,greater<int> > q;
但是，我们为什么这么做呢？其中的各个参数表示什么意思呢？
首先，第一个参数表示数据的类型，第二个参数保存该数据类型数据的容器(默认情况下以vector实现)，第三个参数表示自定义的优先级规则(默认情况下为大根堆，元素大的优先级高)。greater表示数据优先级顺序是从小到大，另外greater也可以改成less，表示数据优先级顺序是从大到小。
注：优先队列其实也就是我们数据结构中学过的堆，默认情况下底层是以vector实现的heap！
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int i;
priority_queue<int,vector<int>,greater<int> > q;
// 向队列中添加元素
q.push(4); q.push(1);
q.push(3); q.push(5);
q.push(6); q.push(2);
int len=q.size(); // 统计优先队列中元素的个数
for(i=0;i<len;i++)
{
// top()返回优先级最高的元素
// 在优先队列中，默认为大根堆，即默认元素大的优先级高
printf("%d ",q.top());
q.pop(); // 删除第一个元素，也即优先级最高的元素
}
printf("\n");
if(q.empty()) // 此时该优先队列中元素已删除完
printf("该优先队列为空\n");
return 0;
}
运行结果：
1 2 3 4 5 6
该优先队列为空
greater变为less的这里不再验证，请有兴趣的童鞋自己验证！
拓展：
优先队列还可以将一个普通数组中的元素转化为优先队列的初始值！
代码如下：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int a[6]={3,2,1,4,6,5};
priority_queue<int> q(a,a+6);
while(!q.empty())
{
printf("%d ",q.top());
q.pop();
}
printf("\n");
return 0;
}
运行结果：
6 5 4 3 2 1
代码2：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int a[6]={3,2,1,4,6,5};
priority_queue<int> q(&a[2],a+6); // &a[2]表示以a[2]的地址为开始地址，a+6表示数组的结束地址
while(!q.empty())
{
printf("%d ",q.top());
q.pop();
}
printf("\n");
return 0;
}
运行结果：
6 5 4 1
如果想自定义优先级并且数据类型不是基本数据类型，而是复杂数据类型，则必须重载其中的operator();
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef struct
{
int a;
int b;
}Node;
// 自定义优先级
struct cmp
{
bool operator()(const Node &t1,const Node &t2)
{
return t1.b<t2.b; // 相当于less，数据元素值大的优先级高
}
};
int main()
{
int i,n;
scanf("%d",&n);
Node *num=new Node[n];
for(i=0;i<n;i++)
{
scanf("%d%d",&num[i].a,&num[i].b);
}
priority_queue<Node,vector<Node>,cmp> q(num,num+n);
while(!q.empty())
{
printf("%d ",q.top().b);
q.pop();
}
printf("\n");
return 0;
}
输入：
3
3 8
5 6
4 7
输出结果：
8 7 6
网友评论