Running Median（对顶堆/动态维护中位数）

题面:

https://ac.nowcoder.com/acm/contest/1001/D

题目大意：

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

思路：

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

代码：

#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;
}

最后

以上就是失眠板凳为你收集整理的Running Median（对顶堆/动态维护中位数）的全部内容，希望文章能够帮你解决Running Median（对顶堆/动态维护中位数）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。