维护一个即时取中位数的队列
这样一个队列，有入队，出队的操作(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()<=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;}