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

我知道，如果即时取最大（小）值的话，可以用两个特殊的栈实现。每个栈里有个附加的栈，用以存储最值

[解决办法]
维护两个堆,两个堆的根就可能是中位数.
然后子叶是一个链表元素.
[解决办法]
平衡树可以解决这个问题，不过太大材小用了，这问题用两个优先队列模拟即可。如下：
设计一个容器，有两种操作：
0 a 表示向容器插入一个元素a
1 表示从容器中弹出一个中位数(有两个中位数时，取低位)
代码如下：

C/C++ code

#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()<=1int 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;}