维护一个即时取中位数的行列

维护一个即时取中位数的队列
这样一个队列，有入队，出队的操作(FIFO)，还要返回中位数值(第k大的数，k = size()/2 + 1)， 这个三个操作速度越快越好

我知道，如果即时取最大（小）值的话，可以用两个特殊的栈实现。每个栈里有个附加的栈，用以存储最值
------解决方案--------------------
维护两个堆,两个堆的根就可能是中位数.
然后子叶是一个链表元素.
------解决方案--------------------
平衡树可以解决这个问题，不过太大材小用了，这问题用两个优先队列模拟即可。如下：
设计一个容器，有两种操作：
0 a 表示向容器插入一个元素a
1 表示从容器中弹出一个中位数(有两个中位数时，取低位)
代码如下：

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<queue>

#include<functional>

using namespace std;

int num; //数字总数

priority_queue<int,vector<int>,less<int> >q1;//存放前(num+1)/2位数字,大的优先出队

priority_queue<int,vector<int>,greater<int> >q2; //存放后(num-1)/2位数字，小的优先出队

//那么中位数就是 q1.top() 并且 0<= q1.size()-q2.size()<=1

int main(){

	int n;

	while(scanf("%d",&n)==1){

		while(!q1.empty()) q1.pop();

		while(!q2.empty()) q2.pop();

		int a,b;

		num=0;

		while(n--){

			 scanf("%d",&a);

			 if(a==0){

				   scanf("%d",&b);

				   num++;

				   if(num==1)

						q1.push(b);

				   else{

					   if(b<=q1.top()){

						   q1.push(b);

						   if(q1.size()-q2.size()>1){

							   q2.push(q1.top());

							   q1.pop();

						   }

					   }

					   else{

						   q2.push(b);

						   if(q1.size()<q2.size()){

							   q1.push(q2.top());

							   q2.pop();

						   }

					   }

				   }

			 }

			 else{

				  if(num==0)

					  puts("No Element!");

				  else{

					  num--;

					  printf("%d\n",q1.top());

					  q1.pop();

					  if(q1.size()<q2.size()){

						  q1.push(q2.top());

						  q2.pop();

					  }

				  }

			 }

		}

		puts("");

	}

 

	return 0;

}