優先隊列是一種相對高級的數據結構，它的底層原理是二叉堆。然而本篇不會執著于深挖其背后的原理，更主要的是理一下它在題目中的一些實用方法，幫助你更快的上手使用。

優先隊列(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)之間解決問題。還有幾道相關的題可以練習一下：

• 264. 丑數 II - 力扣（LeetCode）
• P1090 [NOIP 2004 提高組] 合并果子 - 洛谷
• 506. 相對名次 - 力扣（LeetCode）