Running Median(对顶堆/动态维护中位数)

发布于 2020-07-02  0 次阅读


题面:

Running Median

题目大意:

多组输入,每当输入的个数为奇数时输出此时排序好的中位数。

思路:

使用优先队列的方法建立对顶堆,保持两个二叉堆的数据个数相差不大于1。
当输入个数为奇数时,输出数据个数较大的那一个的top元素。
两个二叉堆的堆顶其中之一必为中位数,因为小根堆小到大,大根堆从大到小,将堆顶放在一起相当于是将一个有序序列从中间断开,断开位置即为中位数。

AC Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int s,t,n,x;
int main(){
    cin>>t;
    while(t--){
        cin>>s;
        cin>>n;
        cout<<s<<" "<<((n+1)/2)<<endl;
        priority_queue<int,vector<int>,greater<int> > qmax;   //greater表示内置类型从大到小排序,大根堆
        priority_queue<int,vector<int>,less<int> > qmin;     //less表示内置类型从小到大排序,小根堆
        cin>>x;
        qmax.push(x);
        cout<<x<<" ";
        for(int i=2;i<=n;i++){ 
            if(i%20==1)
                cout<<endl;
            scanf("%d",&x);

            if(qmax.top()>=x)                                   //根据堆顶决定下一个数字去哪一个堆
                qmin.push(x);
            else
                qmax.push(x);
             
            if(qmax.size()>qmin.size()+1){                      //保持两个堆的数据个数之差不大于一,保持中位数在堆顶
                qmin.push(qmax.top());
                qmax.pop();
            }
            else if(qmax.size()+1<qmin.size()){
                qmax.push(qmin.top());
                qmin.pop();
            }

            if(i%2==1){                                         //为奇数个数时输出中位数
                if(qmax.size()>qmin.size())
                    printf("%d ",qmax.top());
                else
                    printf("%d ",qmin.top());
            }
        }
        cout<<endl;
    }
    return 0;
}

平平无奇的在校大学生