对顶堆例题

例题：洛谷中位数

以下题解来自于 https://www.luogu.com.cn/blog/SeanMoe/solution-p1168

使用两个堆，大根堆维护较小的值，小根堆维护较大的值

即小根堆的堆顶是较大的数中最小的，大根堆的堆顶是较小的数中最大的

将大于大根堆堆顶的数（比所有大根堆中的元素都大）的数放入小根堆，小于等于大根堆堆顶的数（比所有小根堆中的元素都小）的数放入大根堆

那么就保证了所有大根堆中的元素都小于小根堆中的元素

于是我们发现对于大根堆的堆顶元素，有【小根堆的元素个数】个元素比该元素大，【大根堆的元素个数-1】个元素比该元素小；

同理，对于小跟堆的堆顶元素，有【大根堆的元素个数】个元素比该元素小，【小根堆的元素个数-1】个元素比该元素大；

那么维护【大根堆的元素个数】和【小根堆的元素个数】差值不大于1之后，元素个数较多的堆的堆顶元素即为当前中位数；（如果元素个数相同，那么就是两个堆堆顶元素的平均数，本题不会出现这种情况）

根据这两个堆的定义，维护方式也很简单，把元素个数多的堆的堆顶元素取出，放入元素个数少的堆即可

对于部分不会堆的同学，请参照下面各位神犇的算法，或者自行学习堆

下面是代码实现，使用了STL的优先队列作为堆，经过压行仅有24行代码，可读性可能比较低，如果觉得阅读困难可以参照下面各位神犇的代码

#include<bits/stdc++.h>
using namespace std;
int read(){//读入优化
    int x=0;bool f=0;char c=getchar();
    while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
    while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
priority_queue<int,vector<int> > q1;//大根堆
priority_queue<int,vector<int>,greater<int> > q2;//小根堆
int main(){
    int n=read();q1.push(read());
    cout<<q1.top()<<endl; 
    for (int i=2;i<=n;i++){
        int input=read();//等同于cin>>input
        if (input>q1.top()) q2.push(input);
            else q1.push(input);
        while (abs(q1.size()-q2.size())>1)
            if (q1.size()>q2.size()){q2.push(q1.top());q1.pop();}
                else{q1.push(q2.top());q2.pop();}
        if (i%2) cout<<(q1.size()>q2.size()?q1.top():q2.top())<<endl;
    }
    return 0;
}