当前位置：首页 > news >正文

数据结构——优先队列(priority_queue)的巧妙运用

news 2025/7/15 10:44:24

优先队列是一种相对高级的数据结构，它的底层原理是二叉堆。然而本篇不会执着于深挖其背后的原理，更主要的是理一下它在题目中的一些实用方法，帮助你更快的上手使用。

优先队列(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();}
};

通过上面的大概讲解可以了解到：优先队列只能得到此时堆顶的值，但如果我们想找中间值的话就成了麻烦。此时就要介绍一个优先队列的衍生用法：对顶堆。

名字听起来好像是一个什么新的东西，但其实就是把一个优先队列根据题目要求给分成两个优先队列，把题目中要找的那个位置给露出来。接下来用一道例题简单解释一下。

题目：106. 动态中位数 - AcWing题库

题目解析：本题题意也非常的好理解，就是当本序列元素个数为奇数的时候输出此时的中位数。我们都知道，中位数一定要是有序的，所以用优先队列毋庸置疑。但是问题就在于中位数它必须是中间那个数，我们该怎么取呢? 诶，这个时候我们的对顶堆就派上了用场：用一个最小堆维护前一半的序列，再用一个最大堆维护后面那一半。这样就把中位数露出来了。

直接看代码吧，注释写的相对详细：

// 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)之间解决问题。还有几道相关的题可以练习一下：