剑指offer编程题—数据流中的中位数

题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
由于数据是动态插入的，显然不能等所有数据输入结束后进行统一排序。
思路1

1. 维护一个大顶堆和一个小顶堆，并保证如下两个特性：
   1）大顶堆中的所有记录均小于小顶堆中的记录：
   只要保证大顶堆顶元素始终小于小顶堆堆顶元素即可；
   2）大顶堆中总记录数量较小顶堆中的总记录数量，要么大1，要么相等：
   当大顶堆记录总数量较小顶堆中的总记录数量大于2时，取出大顶堆的堆顶元素插入小顶堆，此时两个堆中总记录数量相等；
   当大顶堆记录总数量较小顶堆中的总记录数量小1时，取出小顶堆的堆顶元素插入大顶堆，此时大顶堆记录总数量较小顶堆中的总记录数量大1；
2. 如果从数据流中读出奇数个数值，那么中位数就是大顶堆的堆顶元素；如果从数据流中读出偶数个数值，那么中位数就是大顶堆的堆顶元素与小顶堆的堆顶元素的平均值；

实现手段：C++容器适配器priority_queue<>是一种优先级队列，其排序规则是使用堆排序技术实现的。priority_queue<int,vector<int>,less<int> > 队列中元素并非完全有序，但能保证最大元素总在队头；priority_queue<int,vector<int>,greater<int> >队列原理相同，能保证最小元素总在队头。

class Solution {
public:
    priority_queue<int,vector<int>,less<int> > p; //p中记录按非递增排序，队头值最大
    priority_queue<int,vector<int>,greater<int> > q; //q中记录按非递减排序，队头值最小
    void Insert(int num)
    {
        if(p.empty() || num<=p.top()) p.push(num); //p中维持一个大顶堆，队头元素始终最大
        else q.push(num);
        //输入数据序列总个数为偶数时，保证队列p中记录个数与队列q中记录个数相等
        //输入数据序列总个数为奇数时，保证队列p中记录个数比队列q中记录个数多1
        if(p.size()==q.size()+2){ 
            q.push(p.top());
            p.pop();
        }
        if(p.size()+1==q.size()){
            p.push(q.top());
            q.pop();
        }
    }

    double GetMedian()
    { 
        return p.size()==q.size() ? (p.top()+q.top())/2.0 : p.top();
    }

};