STL—priority_queue

---

一、什么是priority_queue

priority_queue又称为优先队列，其底层是用堆来实现的，优先队列中，队首元素一定是当前队列中优先级最高的哪一个，我们可以在任何时候往队列里插入（push）元素，其优先队列内部会随时做出自我调整，使得每次的队首元素都是优先级最大的，这里的优先级我们可以自己规定，比如规定数字越小优先级越大等等，下文会做出讲解.

要使用优先队列，需要添加头文件#include <queue>

---

二、priority_queue的操作

1.priority_queue的定义

priority_queue<typename> name;

其定义方法和其他的STL容器相同，typename可以是任意基本数据结构或者容器

2.priority_queue容器内元素的访问

和队列不同，优先队列没有front(),back()函数，只能通过top()去访问队首元素（堆顶元素），即优先级最高的元素，q.push(x);是把x插入到队列中

#include <iostream>
#include <queue>using namespace std;int main()
{
    priority_queue<int> q;q.push(5);q.push(7);q.push(1);cout << q.top();return 0;
}

输出结果为：7

3.priority_queue中的函数

（1）push()

q.push(x);令x入队，时间复杂度为O(logN)，N为当前优先队列中的元素个数，实例见priority_queue容器内元素的访问

（2）top()

q.top();可以获得队首元素（堆顶元素），时间复杂度为O(1)，实例见priority_queue容器内元素的访问

（3）pop()

q.pop();令队首元素（堆顶元素）出队，时间复杂度为O(logN)，N为当前优先队列中的元素个数

#include <iostream>
#include <queue>using namespace std;int main()
{
    priority_queue<int> q;q.push(5);q.push(7);q.push(1);cout << q.top() << endl;q.pop();cout << q.top();return 0;
}

输出结果为：
7
5

（4）empty()

q.empty();用来检测队列是否为空，返回true为空，返回false则非空，时间复杂度为O(1)

#include <iostream>
#include <queue>using namespace std;int main()
{
    priority_queue<int> q;if(q.empty()) cout << "EMPTY" << endl;else cout << "NOT EMPTY" << endl;for (int i = 1; i <= 5; i ++ ) q.push(i);if(q.empty()) cout << "EMPTY" << endl;else cout << "NOT EMPTY" << endl;return 0;
}

输出结果为：
EMPTY
NOT EMPYTY

（5）size()

q.size();返回优先队列内的元素个数，时间复杂度为O(1)

#include <iostream>
#include <queue>using namespace std;int main()
{
    priority_queue<int> q;q.push(5);q.push(7);q.push(1);cout << q.size();return 0;
}

输出结果为：3

4.priority_queue内元素优先级的设置

基本数据结构类型的优先级设置

我们知道，优先队列都是默认把字典序（数字）大的放到队首（堆顶），如果我们想要把最小的元素放在队首的话，可以如下定义：

priority_queue<int, vector<int>, greater<int>> q;     //把最小的元素放在堆顶的定义方法
priority_queue<char, vector<char>, greater<char>> q;  //把字典序最小的元素放在堆顶的定义方法
//上述两式如果报错的话可以写成：
priority_queue<int, vector<int>, greater<int> > q; 
priority_queue<char, vector<char>, greater<char> > q;

下面是一个例子：

#include <iostream>
#include <queue>using namespace std;int main()
{
    priority_queue<char, vector<char>, greater<char>> q;q.push('c');q.push('a');q.push('d');cout << q.top();return 0;
}

输出结果为：a

结构体的优先级设置

在这里首先强调一下如果用结构体 + 优先队列对结构体进行内部排序的效果和sort + 结构体的作用效果是相反的，即我们如果按照下述例子比如按照区间的左顶点从小到大进行排序的模板写到sort排序中，那么就是按照区间的左顶点从大到小进行排序，这里读者只需要明确这一点就好了，本章介绍的是结构体 + 优先队列，对sort不进行讲解，sort函数的讲解见博客：STL—algorithm（2）

我们这里举一个区间的例子，比如我们对区间的左顶点和右定点建立一个结构体

struct Range
{
    int l, r;
}range[N];

现在我们希望我们按照区间的左顶点从小到大进行排序，则写成：

struct Range
{
    int l, r;bool operator < (const Range w) const{
    return l > w.l;}
}range[N];

如果我们希望我们按照区间的左顶点从大到小进行排序，则写成：

struct Range
{
    int l, r;bool operator < (const Range w) const{
    return l < w.l;}
}range[N];

举一个例子：现在给三个水果的名字和价格，要求按照水果价格从高到低进行排序

#include <iostream>
#include <cstring>
#include <queue>using namespace std;struct fruit{
    string n;int p;bool operator < (const fruit w) const{
    return p < w.p;}
}f[3];int main()
{
    priority_queue<fruit> q;f[0].n = "桃子";f[0].p = 2;f[1].n = "梨";f[1].p = 4;f[2].n = "苹果";f[2].p = 1;for (int i = 0; i < 3; i ++ ) q.push(f[i]);auto t = q.top();cout << t.n << ' ' << t.p;return 0;
}

输出结果：梨 4

现在给三个水果的名字和价格，要求按照水果价格从低到高进行排序

#include <iostream>
#include <cstring>
#include <queue>using namespace std;struct fruit{
    string n;int p;bool operator < (const fruit w) const{
    return p > w.p;}
}f[3];int main()
{
    priority_queue<fruit> q;f[0].n = "桃子";f[0].p = 2;f[1].n = "梨";f[1].p = 4;f[2].n = "苹果";f[2].p = 1;for (int i = 0; i < 3; i ++ ) q.push(f[i]);auto t = q.top();cout << t.n << ' ' << t.p;return 0;
}

输出结果：苹果 1