优先队列是一种相对高级的数据结构，它的底层原理是二叉堆。然而本篇不会执着于深挖其背后的原理，更主要的是理一下它在题目中的一些实用方法，帮助你更快的上手使用。
优先队列(priority_queue)
优先队列的特别之处就在于它可以自动进行排序，很好的维护了整个序列内的单调性，比如一个初始的大顶堆：priority_queue<int>.它自顶向下是呈递减的, 也就是说它的堆顶的元素永远都是最大的。这可以非常方便的处理有关序列单调性的问题。如果想实现最小堆这样定义：priority_queue<int, vector<int>, greater<int>>。接下来就说一下具体使用方法和场景。
| q.push(val) | 将值压进去 |
| q.emplace(val) | 创造一个值压进去 |
| q.pop() | 将堆顶值弹出去 |
| q.size() | 整个堆的大小 |
| q.empty() | 判断堆是否为空 |
先看一个经典的题目：703. 数据流中的第 K 大元素 - 力扣（LeetCode）
题目非常的好懂，就是不停的增加序列的个数，每次输出第K大的数字。由于数字不停的在增加，如果每次都进行排序那么略显浪费。但是我们的优先队列只能读取第一个元素。要想解决快速找到第K个，不妨先定义一个最小堆，控制堆的大小为K，这样堆顶就一直是这K个中最小的了。思路上进行了一个小转变，可以O(1)查到第K大的数字，非常的便捷。
Code:
class KthLargest {
public:
priority_queue<int, vector<int>, greater<int>> Q;
int k1;
KthLargest(int k, vector<int>& v) {
k1 = k;
for (int num : v)
add(num);
}
int add(int val)
{
Q.push(val);
if (Q.size() > k1)
Q.pop();
return Q.top();
}
};通过上面的大概讲解可以了解到：优先队列只能得到此时堆顶的值，但如果我们想找中间值的话就成了麻烦。此时就要介绍一个优先队列的衍生用法：对顶堆。
名字听起来好像是一个什么新的东西，但其实就是把一个优先队列根据题目要求给分成两个优先队列，把题目中要找的那个位置给露出来。接下来用一道例题简单解释一下。
题目解析：本题题意也非常的好理解，就是当本序列元素个数为奇数的时候输出此时的中位数。我们都知道，中位数一定要是有序的，所以用优先队列毋庸置疑。但是问题就在于中位数它必须是中间那个数，我们该怎么取呢? 诶，这个时候我们的对顶堆就派上了用场：用一个最小堆维护前一半的序列，再用一个最大堆维护后面那一半。这样就把中位数露出来了。
直接看代码吧，注释写的相对详细：
// Problem: 动态中位数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/108/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define endl '\n'
const int N = 1e6+5;
//1、多实例清变量！！！
//2、N范围变了没？
//3、是否开多实例？
//4、用字符串如果是两位数呢？
//5、没输入完不要退出！
priority_queue<int, vector<int>, greater<int>> Q;
priority_queue<int> q;
int n,m;
int a[N];
int x;
void solve()
{
Q = priority_queue<int, vector<int>, greater<int>>();
q = priority_queue<int>();
vector<int> v;
cin >> n >> m;
cin >> x,q.push(x);
v.push_back(q.top());//先将第一个数压进去
for(int i=2; i<=m; i++)
{
cin >> x;
Q.push(x);//其实随便压一个就好了
while(q.top()>Q.top())//保证Q整体是>=q的
{
int t=Q.top();
Q.pop();
Q.push(q.top());
q.pop();
q.push(t);
}
while(Q.size()>q.size())//调整大小,让q的大小始终比Q多一个
{
q.push(Q.top());
Q.pop();
}
while(q.size()>Q.size()+1)
{
Q.push(q.top());
q.pop();
}
if(i%2==1)//当为奇数个的时候输出
v.push_back(q.top());
}
cout << n << ' ' << m/2+1 << endl;
int sum=0;
for(auto i:v)
{
cout << i << ' ';
sum++;
if(sum==10)//调整格式,保证一行最多10个
{
cout << endl;
sum=0;
}
}
if(sum!=0)
cout << endl;
v.clear();//清变量~
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
cin >> t;
while(t--) solve();
return 0;
}总得来说，优先队列由于其自动排序的特点使得它非常的好用，一般可以在O(n)~O(nlogn)之间解决问题。还有几道相关的题可以练习一下：