1.前言
在今天的做题过程中遇见了这样一类问题：
动态维护n个数中的 第k大的数 / 第k小的数 / 中位数
一开始没有什么思路，然后尝试每加入一个数用一次sort然后输出所要求的的数，不出意外爆掉了，在补题的时候看到了对顶堆这种非常优秀的数据结构，所以 学完写一篇博客，持续更新；
2.实现原理
我们用STL中的 单调队列大根堆和小根堆来实现对顶堆；
对顶堆由一个小根堆和一个大根堆组成，维护小根堆堆顶为第 k 大的元素，大于它的放在小根堆，小于它的放入大根堆
priority_queue< int > maxp;//大根堆
priority_queue<int,vector< int >,greater< int > >minp;//小根堆
在小根堆里维护小根堆堆顶为 第 k 大个元素
（维护中位数是维护第 k 大个元素的一个特例，维护第 k 小个元素即是维护第（n-k）大个元素）
1.元素的插入：
当我们有一个元素之后，我们是选择放入大根堆还是放入小根堆呢，我们在这里把小根堆堆顶作为一个标志（后面的实现会给出用大根堆堆顶做标志的不方便之处），大于它的放入小根堆，否则放入大根堆，等于它的放在哪里都可，因为对后面维护没影响，这样插入就保证了整个对顶堆的数据整体的有序性，一开始把第一个元素作为标志元素，方便维护；
void push(int num) { if(num>=minp.top())//小根堆堆顶做标志 minp.push(num); else maxp.push(num); trans();//每插入一个数据维护一次 }
2.元素的维护：
每次放入一个元素后我们都要做一次维护，维护很简单，因为整体元素已经有序，我们只要保证小根堆中的元素恰好为 k 个即可。少元素在大根堆堆顶取出，否则把自己堆顶元素放入大根堆
void trans() { while(minp.size()<now)//now为k，即要维护的第k大，不够就去大根堆中取 { minp.push(maxp.top()); maxp.pop(); } while(minp.size()>now)//多了就往大根堆放 { maxp.push(minp.top()); minp.pop(); } }
3.例题
1.洛谷P7072 直播获奖
题目大意：
根据题中给出人数与分数线的关系动态维护第 k 大的元素；
priority_queue<int> maxp; priority_queue<int,vector<int>,greater<int>>minp; int n,w,now,num; void trans()//维护 { while(minp.size()<now) { minp.push(maxp.top()); maxp.pop(); } while(minp.size()>now) { maxp.push(minp.top()); minp.pop(); } } void push(int num)//插入 { if(num>=minp.top()) minp.push(num); else maxp.push(num); trans(); } int main() { scanf("%d %d",&n,&w); scanf("%d",&num); minp.push(num); printf("%d ",minp.top());//把第一个元素放在小根堆堆顶做标志元素，同时根据题意，当只有一个元素时第一个元素一定是分数线 for (int p=2;p<=n;p++) { now=max(1,p*w/100);//整除就是小数的向下取整，不会出现误差 scanf("%d",&num); push(num); printf("%d ",minp.top()); } return 0; }
2.洛谷P3871 中位数
题目大意：
动态维护中位数
根据题意，无论我们要维护的数总数为奇还是为偶
我们要的 k 总为( n / 2 ) + 1;
priority_queue<ll>maxq; priority_queue<ll,vector<ll>,greater<ll>>minq; ll n; ll num,now; ll m,cnt; string s; void trans()//维护 { while(minq.size()>now) { maxq.push(minq.top()); minq.pop(); } while(minq.size()<now) { minq.push(maxq.top()); maxq.pop(); } } void push(int num)//插入 { if(num>=minq.top()) minq.push(num); else maxq.push(num); trans(); } int main() { cin>>n; scanf("%lld",&num); minq.push(num);// n 必然大于 0 ，因此我们把第一个数作为标志元素 for(int i=2;i<=n;i++) { scanf("%lld",&num); now=i/2+1; push(num); }//把 n 个元素插入并维护 cin>>m; for(int i=1;i<=m;i++) { cin>>s; if(s=="add") { cnt++; now=(cnt+n)/2+1; scanf("%lld",&num); push(num);//记录新插入元素的个数，并维护对顶堆 } else { printf("%lld\n",minq.top());//维护的小根堆的堆顶即为中位数 } } return 0; }
这里我们给出用大根堆堆顶作为标志的不方便之处
假如 n = 1；然后不插入直接查询，我们让大根堆堆顶作为标志的话，小根堆是空的最后还要特判，不如直接使用小根堆堆顶做插入标志方便，同时小根堆堆顶还是最后维护的值，比较好记；
4.拓展
当遇到不是动态维护第 k 大元素的时候，而仅仅是求一个无规则数列中的第 k 大的数时，我们可以借助STL中的 nth_element这个函数来实现
nth_element的作用是求第 k 小的元素，我们稍加改造就能求第 k 大的元素
它会使第 k 小的元素归位，使它前边的元素小于它，使它后面的元素大于它；
它的用法是
nth_element(a+x,a+x+y,a+x+len);
能使下标从 x 到 x+y-1 的元素小于 x+y 从 x+y+1 到 x+y+len 的元素大于 x+y；
时间复杂度只有 O(n)，十分好用
例题链接 洛谷P1923 求第k小的数
本人是新手，有什么错误欢迎指出~
