C++ STL容器  优先队列(priority_queue)用法详解

常见用途

1，可以解决一些贪心问题；

2，也可以对dijksta算法进行优化；

既然是队列那么先要包含头文件#include <queue>,

其底层是用堆来进行实现的

在优先队列中，优先队列本身默认的规则就是优先级高的放在队首

 

先举个例子（假设数字小的优先级高）：

原先队列中有

 

现在插入一个数

 

优先队列会在容器中自动排序

    

---

---

 

定义：priority_queue<Type, Container, Functional>

Type 就是数据类型。（int ，double等.)

Container 就是容器类型（Container必须是用数组实现的容器，默认vector，但不能用 list。）

Functional 就是比较的方式（可以自定义，默认从小到大排序）

关于自定义排序方式接下来会有说明

 

 

一般声明有
priority_queue <int> p1;
priority_queue <double> p2;复制

• 下面是一些常用的操作：

1.top  访问队头元素   （ 在优先队列中，没有 front() 函数与 back() 函数 ）

2.push 插入元素到队尾

3.pop 弹出队头元素

4.empty 队列是否为空

5.size 返回队列内元素个数

6.swap 交换内容

 

• 基本类型的比较：int 型，double 型，char 型等

• 优先级对它们的设置默认都是数字大的优先级越高

  队首元素就是优先队列内元素最大的那个

#include <iostream>
#include<queue>
using namespace std;
int a[1000010];
int main()
{
    priority_queue<int> a;//默认为降序排序
    //等价于 priority_queue<int,vector<int> , less<int> >q;
    a.push(5);
    a.push(10);
    a.push(15);
    a.push(1);
    while(!a.empty())
    {
        cout<<a.top()<<' ';
        a.pop();
    }
    return 0;
}
复制

 

 

• 关于字符 的比较 

字符中就是字典序最大

#include <iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<string> a;//默认为降序排序
    a.push("abc");
    a.push("abcd");
    a.push("cbd");
    a.push("abcde");
    while(!a.empty())
    {
        cout<<a.top()<<' ';
        a.pop();
    }
    return 0;
}
复制

 

• pari的比较，先比较第一个元素，第一个相等比较第二个

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //以下代代码返回pair的比较结果，先按照pair的first元素降序，
    //first元素相等时，再按照second元素降序：
    priority_queue<pair<int,int> >p;
    pair<int,int> a(3,4);
    pair<int,int> b(3,5);
    pair<int,int> c(4,3);
    p.push(a);
    p.push(b);
    p.push(c);
    while(!p.empty())
    {
        cout<<p.top().first<<"\t"<<p.top().second<<endl;
        p.pop();
    }
    return 0;
}

复制

 

• 自定义数据类型的比较

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int x;
    Node() {}
    Node(int x):x(x) {} //赋值
    bool operator<(const Node& a) const//从大到小
    {
        return x<a.x;
    }
};
int main()
{
    priority_queue<Node> p;
    for(int i=1; i<=5; i++)//输入数据
        p.push(Node(i));
    while(!p.empty())
    {
        cout<<p.top().x<<' ';
        p.pop();
    }
    return 0;
}
复制

*****刚刚入门的小伙伴们第一接触的话看到这就可以了，下 面是关于优先队列的进一步运用*****

 

---

---

虽然有限队列有默认的排列顺序，但在很多情况下默认排序并不满足我们的需求，这就需要我们们自定义排列顺序

less<int>表示数字大的优先级越大
greater<int>表示数字小的优先级越大

下面两种优先队列的定义是等价的（以int型为例）
priority_queue<int>q;
priority_queue<int,vector<int> , less<int> >q;（把元素最小的元素放在队首）
 

• 　可以在结构体内部重载运算符，改变符号号的功能

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int x;
    Node() {}
    Node(int x):x(x) {} //赋值
    bool operator<(const Node& a) const //从大到小
    {
        return x<a.x;
    }
    bool operator>(const Node& a) const//从小到大
    {
        return x>a.x;
    }
};
int main()
{
    priority_queue<Node> p1;//默认从大到小 等价于priority_queue<Node,vector<Node>,less<Node> > p1;
    for(int i=1; i<=5; i++)
        p1.push(Node(i));
    cout<<"p1 = ";
    while(!p1.empty())
    {
        cout<<p1.top().x<<' ';
        p1.pop();
    }
    cout<<endl;
  
  
  
    priority_queue<Node,vector<Node>,greater<Node> > p2;//从小到大
    for(int i=5; i>=1; i--)
        p2.push(Node(i));
    cout<<"p2 = ";
    while(!p2.empty())
    {
        cout<<p2.top().x<<' ';
        p2.pop();
    }
    return 0;
}
复制

 

• 　可以在结构体内部重载运算符，改变符号号的功能

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int x;
    Node() {}
    Node(int x):x(x) {} //赋值
};
struct cmp
{
    /*bool operator() (const Node& a,const Node& b) //从大到小
    {
        return a.x<b.x;
    }*/
    bool operator() (const Node& a,const Node& b) //从小到大
    {
        return a.x>b.x;
    }

};

int main()
{
    priority_queue<Node,vector<Node>,cmp > p;
    for(int i=1; i<=5; i++)
        p.push(Node(i));
    cout<<"p = ";
    while(!p.empty())
    {
        cout<<p.top().x<<' ';
        p.pop();
    }
    cout<<endl;
    return 0;
}
复制