维护一个即刻取中位数的队列

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

维护一个即刻取中位数的队列

相关推荐