数据流中位数

题目描述:

给一个源源不断的数据流，每次输入一个数输出现有数字的中位数

分析： 采用优先级队列构造一个大根堆，一个小根堆，输入的数据存入大根堆或者小根堆，当两个堆的数据数量大于1时，存入数量少的堆，因为大根堆和小根堆是有大小的，中位数就在堆顶产生，那个堆数据多一个，中位数就是那个堆顶元素，如果两个堆数量相等，就取各自的堆顶元素求平均数即是中位数。

#include<iostream>
#include<functional> 
#include<queue>
#include<vector>
using namespace std;

int main(){
	priority_queue<int, vector<int>, less<int> > que1;//大根堆 
	priority_queue<int, vector<int>, greater<int> >que2;//小根堆 
	int a[]={14,10,56,7,83,22,36,91,3,47,72,0};
/*	for(int i=0;a[i];i++){
		que1.push(a[i]);
	}
	*/
	for(int i=0;a[i];i++){
		que1.push(a[i]);
		if(que1.size() - que2.size() >1){
			int k = que1.top();
			que1.pop();
			que2.push(k);
		}
		if(que1.empty()){
			cout<<que2.top()<<endl;
		}
		else if(que2.empty()){
			cout<<que1.top()<<endl;
		}else
		cout<<(que1.top() + que2.top())/2<<endl;
	}

/*	while(!que1.empty()){
		printf("%d",que1.top());
		que1.pop();
		cout<<"\n";
		}
		
		cout<<"\n";
	while(!que2.empty()){
		printf("%d",que2.top());
		que2.pop();
		cout<<"\n";
		}
*/
}