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

首先，你需要

#include<queue>
using namespace std;

这两个头文件。

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

priority_queue <int> i;
priority_queue <double> d;

不过，我们最为常用的是这几种：

priority_queue <node> q;
//node是一个结构体
//结构体里重载了‘<’小于符号
priority_queue <int,vector<int>,greater<int> > q;
//不需要#include<vector>头文件
//注意后面两个“>”不要写在一起，“>>”是右移运算符
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<cstdio>
#include<queue>
using namespace std;
priority_queue <int> q;
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<a.x;
    }
};

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

#include<cstdio>
#include<queue>
using namespace std;
struct node
{
    int x,y;
    bool operator < (const node & a) const
    {
        return x<a.x;
    }
}k;
priority_queue <node> 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)

它也是按照重载后的小于规则，从大到小排序
注意:只能重载<号,从小到大要把<重载成>

注意:如果要多级排序,可以这样写:

#include<cstdio>
#include<queue>
using namespace std;
struct node{
    int x,y;
    bool operator < (const node & a) const{
        if (x==a.x) return y>a.y;
        return x>a.x;
    }
}k;
priority_queue <node> 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=8,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);
    }
}

less 和 greater 优先队列

还是以 int 为例，先来声明：

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

话不多说，上程序和结果：

#include<cstdio>
#include<queue>
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<int>:")
    while(!p.empty())
        printf("%d ",p.top()),p.pop();  

    pritntf("\ngreater<int>:")
    while(!q.empty())
        printf("%d ",q.top()),q.pop();
}

结果：
less<int>:14 12 10 8 6 greater<int>:6 8 10 12 14

所以，我们可以知道，less 是从大到小，greater 是从小到大。
平时建议写:

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

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/36/