概述
一、优先队列介绍
优先队列也属于队列,所以在使用时同样要包含头文件#include< queue >,优先队列常用于分支限界法、宽度优先搜索,队列执行入队或者出队后内部会自动调整按优先级排列的顺序,即每次出队的都是优先级最高的,和堆排序中堆的调整类似。优先队列主要包含以下几种操作:
push() 插入元素到队尾 (并排序)
pop() 弹出队头元素(自动调整)
top() 访问队头元素
empty() 队列是否为空
size() 返回队列内元素个数
emplace() 原地构造一个元素并插入队列
swap() 交换内容
二、使用举例
1.声明优先队列
priority_queue<type,vector<type>,comp>Q;
第一个参数type是数据类型
第二个是容器类型,STL默认容器是vector
第三comp个是比较函数,如果没有此参数,默认大根堆,即降序排列
测试代码
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int D[10];
priority_queue<int,vector<int> >T;//这里注意要多打一个空格
for(int i=0;i<10;i++)
{
D[i]=(i*10/3+372)%20;//随意获取10个数
printf("%d ",D[i]);
T.push(D[i]);
}
printf("n----------分割线-----------n");
while(!T.empty())
{
int s=T.top();
printf("%d ",s);
T.pop();//出队
}
return 0;
}
运行结果
12 15 18 2 5 8 12 15 18 2
----------分割线-----------
18 18 15 15 12 12 8 5 2 2
2.默认比较参数模板
有时候我们需要升序排列,有时候需要降序排列,有时候数据类型类结构体,数据元素不止一个,需要根据我们想要的方式排序,这就要用到比较函数,这也是实现优先队列优先级的一个标准。
系统提供升序比较函数greater< type >,降序比较函数less< type>
测试代码
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int D[10];
priority_queue<int,vector<int>,greater<int> >T;//小根堆
//priority_queue<int,vector<tmp>,less<int> >T;//这样是大根堆
for(int i=0;i<10;i++)
{
D[i]=(i*10/3+372)%20;//随意获取10个数
printf("%d ",D[i]);
T.push(D[i]);
}
printf("n----------分割线-----------n");
while(!T.empty())
{
int s=T.top();
printf("%d ",s);
T.pop();//出队
}
return 0;
}
运行结果
12 15 18 2 5 8 12 15 18 2
----------分割线-----------
2 2 5 8 12 12 15 15 18 18
3.用户自定义比较类型comp
大多数时候,我们再进行宽度优先搜索时,队列元素往往不只一个,比如队列元素为坐标,是根据横坐标比较还是纵坐标比较,还是先横坐标,横坐标相同再根据纵坐标排等,这就需要用户自定义比较函数来进行优先队列的排序。
一般来说,自定义comp都是类或者结构体,里面重载运算符来进行比较,比如对于二元组
(
x
,
y
)
(x,y)
(x,y),要根据
x
x
x排序,则可这样定义comp
struct tmp
{
int x,y;
};
struct comp
{
int x;
bool operator()(tmp &a,tmp &b)
{
return a.x<b.x;
}
};
若需要现根据 x x x排序, x x x相同再根据 y y y排序,则可如下定义comp
struct tmp
{
int x,y;
};
struct comp
{
int x;
bool operator()(tmp &a,tmp &b)
{
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
};
根据 y y y的值降序排序的测试代码如下(其余排序标准类似)
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct tmp
{
int x,y;
};
struct comp
{
int x;
bool operator()(tmp &a,tmp &b)
{
return a.y<b.y;
}
};
int main()
{
struct tmp D[10];
priority_queue<tmp,vector<tmp>,comp>T;
for(int i=0;i<10;i++)
{
D[i].x=(i*10/3+372)%20;
D[i].y=(i*14560/3+372)%20;
printf("(%d,%d)n",D[i].x,D[i].y);
T.push(D[i]);
}
printf("n----------分割线-----------n");
while(!T.empty())
{
tmp s=T.top();
printf("(%d,%d)n",s.x,s.y);
T.pop();
}
return 0;
}
运行结果
(12,12)
(15,5)
(18,18)
(2,12)
(5,5)
(8,18)
(12,12)
(15,5)
(18,18)
(2,12)
----------分割线-----------
(18,18)
(8,18)
(18,18)
(12,12)
(12,12)
(2,12)
(2,12)
(15,5)
(5,5)
(15,5)
最后
以上就是不安鼠标为你收集整理的C++优先队列的使用方法的全部内容,希望文章能够帮你解决C++优先队列的使用方法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复