优先队列priority_queue详解

发布时间:2018-10-29 17:55:57 作者:ex_jason 阅读量:126

优先队列priority_queue详解

“Crl最好了!”。(=QωQ=)

优先队列

引入

优先队列是一种特殊的队列,在学习堆排序的时候就有所了解,查看

那么优先队列是什么呢? 
说白了,就是一种功能强大的队列。如果不太清楚队列,可以看看这篇博客

它的功能强大在哪里呢? 
四个字:自动排序

优先队列的头文件&&声明

首先,你需要

#include

using namespace std;

这两个头文件。

其次,一个优先队列声明的基本格式是: 
priority_queue<结构类型> 队列名; 
比如:

priority_queue <int> i;

priority_queue <double> d;

不过,我们最为常用的是这几种:

priority_queue q;

//node是一个结构体

//结构体里重载了‘<’小于符号

priority_queue <int,vector<int>,greater<int> > q;

//不需要#include头文件

//注意后面两个“>”不要写在一起,“>>”是右移运算符

priority_queue <int,vector<int>,less<int> >q;

我们将在下文来讲讲这几种声明方式的不同。

优先队列的基本操作

与队列的基本操作如出一辙。 

以一个名为q的优先队列为例。

q.size();//返回q里元素个数

q.empty();//返回q是否为空,空则返回1,否则返回0

q.push(k);//在q的末尾插入k

q.pop();//删掉q的第一个元素

q.top();//返回q的第一个元素

q.back();//返回q的末尾元素

优先队列的特性

上文已经说过了,自动排序。 
怎么个排法呢? 
在这里介绍一下:

默认的优先队列(非结构体结构)

priority_queue <int> q;

这样的优先队列是怎样的?让我们写程序验证一下。

#include

#include

using namespace std;

priority_queue <intq;

int main()

{

    q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);

    while(!q.empty())

        printf("%d ",q.top()),q.pop();

}

程序大意就是在这个优先队列里依次插入10、8、12、14、6,再输出。 
结果是什么呢? 
14 12 10 8 6 
也就是说,它是按从大到小排序的!

默认的优先队列(结构体,重载小于)

先看看这个结构体是什么。

struct node

{

    int x,y;

    bool operator < (const node & a) const

    {

        return x

    }

};

这个node结构体有两个成员,x和y,它的小于规则是x小者小。 
再来看看验证程序:

#include

#include

using namespace std;

struct node

{

    int x,y;

    bool operator < (const node & a) const

    {

        return x.x;

    }

}k;

priority_queue q;

int main()

{

    k.x=10,k.y=100; q.push(k);

    k.x=12,k.y=60; q.push(k);

    k.x=14,k.y=40; q.push(k);

    k.x=6,k.y=80; q.push(k);

    k.x=8,k.y=20; q.push(k);

    while(!q.empty())

    {

        node m=q.top(); q.pop();

        printf("(%d,%d) ",m.x,m.y);

    }

}

程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)这五个node。 
再来看看它的输出: 
(14,40) (12,60) (10,100) (8,20) (6,80)

它也是按照重载后的小于规则,从大到小排序的。

less和greater优先队列

还是以int为例,先来声明:

priority_queue <int,vector<int>,less<int> > p;

priority_queue <int,vector<int>,greater<int> > q;

话不多说,上程序和结果:

#include

#include

using namespace std;

priority_queue <int,vector<int>,less<int> > p;

priority_queue <int,vector<int>,greater<int> > q;

int a[5]={10,12,14,6,8};

int main()

{

    for(int i=0;i<5;i++)

        p.push(a[i]),q.push(a[i]);

 

    printf("less:")

    while(!p.empty())

        printf("%d ",p.top()),p.pop();  

 

    pritntf("\ngreater:")

    while(!q.empty())

        printf("%d ",q.top()),q.pop();

}

结果: 

less:14 12 10 8 6 
greater:6 8 10 12 14

所以,我们可以知道,less是从大到小,greater是从小到大

作个总结

为了方便,在平时,建议大家写:

priority_queue<int,vector<int>,less<int> >q;

priority_queue<int,vector<int>,greater<int> >q;

平时如果用从大到小不用后面的vector,less,可能到时候要改成从小到大,你反而会搞忘怎么写greater,反而得不偿失。

总结

优先队列到此就作了个小结。 
其实不管是队列,还是优先队列,都不仅仅只有我讲的这些,还有更多可以探索。

上一篇:
下一篇:快速排序

我要评论 登录后才能发布评论

推荐阅读

 2018-11-17 14:31:12   ex_jason

最小生成树

 2018-11-10 20:40:14   ex_jason

LOL S8 决赛视频

 2018-11-10 07:41:45   ex_jason

并查集

 2018-11-10 07:28:04   ex_jason

写代码的小女孩

 2018-11-09 20:18:38   ex_jason

谈谈关于初赛的那些事

 2018-11-09 20:03:06   ex_jason

dijkstra 详解

  文章归档

ex_jason的博客"    我要留言
Catfish(鲶鱼) CMS V 4.8.39