对顶堆
由一个大根堆和一个小根堆组成，小根堆里面的数永远比大根堆里面的数要大
用途：用于动态维护区间内第k大的数，要比线段树和动态平衡树写起来更简单
比如说我们要维护第k大的数，那么我们肯定是将前k大的数放进小根堆，小根堆的堆顶就是第k大的数
我们来看一下维护第k大的数的代码
1.建立大根堆和小根堆
priority_queue<int> qmax; //相当于大顶堆
priority_queue<int,vector<int>,greater<int>> qmin; //相当于小顶堆2.如果小根堆是空的，或者说当前元素大于小根堆的堆顶元素，那么就将当前元素存入小根堆，否则就存入大根堆
if(qmin.empty()||a>=qmin.top()){qmin.push(a);}else{qmax.push(a);}3.大、小根堆的维护，当我们小根堆的元素，不满k个，就将大根堆的堆顶元素弹入小根堆，如果我们当前小根堆的元素超过了k个，就将小根堆的堆顶元素摊入大根堆
while(qmin.size()>k){qmax.push(qmin.top());qmin.pop();}while(qmin.size()<k&&!qmax.empty()){qmin.push(qmax.top());qmax.pop();}4.查询第k大的元素，访问小根堆的堆顶元素
cout<<qmin.top()<<"\n";例题
P1168 中位数
思路：去求奇数项的中位数，这个中位数的下标是在不断变化的，很板的一种动态维护第k大的元素的板题，直接套用对顶堆代码即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int a;
priority_queue<int> qmax;
priority_queue<int,vector<int>,greater<int> > qmin;
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a;if(i%2==1){k=(i+1)/2;}if(qmin.empty()||a>=qmin.top()){qmin.push(a);}else{qmax.push(a);}while(qmin.size()>k){qmax.push(qmin.top());qmin.pop();}while(qmin.size()<k&&!qmax.empty()){qmin.push(qmax.top());qmax.pop();}if(i%2==1){cout<<qmin.top()<<"\n";}}return 0;
}
P7072 [CSP-J2020] 直播获奖
思路：第一眼看上去，获奖分数线为多少？即i*w/100位置上的人的分数是多少，翻译过来还是第k大的元素是多少，动态维护第k大的对顶堆板题
直接写就行
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
double w;
int a;
priority_queue<int>qmax;
priority_queue<int,vector<int>,greater<int> >qmin;
signed main()
{cin>>n>>w;for(int i=1;i<=n;i++){cin>>a; int z=floor(i*w/100);k=max(1LL,z);if(qmin.empty()||a>=qmin.top()){qmin.push(a);}else{qmax.push(a);}while(qmin.size()<k&&!qmax.empty()){qmin.push(qmax.top());qmax.pop();}while(qmin.size()>k){qmax.push(qmin.top());qmin.pop();}cout<<qmin.top()<<" ";}return 0;
} P2085 最小函数值
思路：我们发现a,b,c都是正数，那么其堆成周-b/2*a,永远都在负数的位置，也就是说，这n个函数，在0~正无穷内都是单调递增的，那么我们可以考虑一种剪枝的O(n*m)的写法，我们首先创建一个大顶堆，存储前k小的元素，我们在最外层遍历n个函数，内层遍历m个数，当n为1的时候，先将m个函数值存进去，然后当后续的函数，如果存在比堆顶元素小的，就存进大顶堆，弹出堆顶
,如果比堆顶元素大，那就立刻结束当前内层循环，因为后面也会比堆顶元素大，。
直到双重循环遍历完，然后输出倒序前m个即可
//P2085 最小函数值
#include<bits/stdc++.h>
using namespace std;
#define int long longint n,m;
priority_queue<int>qmax;
int a,b,c;
int f;
int ans[200005];
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a>>b>>c;for(int j=1;j<=m;j++){f=a*j*j+b*j+c;if(i==1){qmax.push(f);}else{if(f<qmax.top()){qmax.pop();qmax.push(f);}else{break;}}}}for(int i=1;i<=m;i++){ans[i]=qmax.top();qmax.pop();}for(int i=m;i>=1;i--){cout<<ans[i]<<" ";}return 0;
}P1631 序列合并
思路：和上面那个一个思路，我们写一个有剪枝的O(n^2)的写法 ，和上面那个思路差不多
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int b[100005];
int ans[100005];
priority_queue<int> q;
signed main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];sort(a+1,a+1+n);sort(b+1,b+1+n);int k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){k=a[i]+b[j];if(i==1){q.push(k);}else{if(k<q.top()){q.pop();q.push(k);}else{break;}}}}for(int i=1;i<=n;i++){ans[i]+=q.top();q.pop();}for(int i=n;i>=1;i--)cout<<ans[i]<<" ";return 0;
}P1801 黑匣子
思路：我们很容易发现，题目还是动态求第k小的，因此我们要将前k小的，放入大根堆中，当我们大根堆位空，或者说当前元素小于大根堆的堆顶，就存进来，我们用vis[i]去统计要进行输出的位置即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int a[200005];
int b[200005];
int vis[200005];
priority_queue<int> qmax;
priority_queue<int,vector<int>,greater<int> > qmin;signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];vis[b[i]]++;}int k=0;for(int i=1;i<=n;i++){if(qmax.empty()||a[i]<qmax.top()){qmax.push(a[i]);}else{qmin.push(a[i]);}while(vis[i]){k++;while(qmax.size()<k){qmax.push(qmin.top());qmin.pop();}while(qmax.size()>k){qmin.push(qmax.top());qmax.pop();}cout<<qmax.top()<<"\n";vis[i]--;}}return 0;
}
