题目描述

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

样例

输入：1, 2, 3, 4

输出：1,1.5,2,2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

背景知识

大顶堆：完全二叉树，任意非叶子节点的值大于等于其子节点的值。
小顶堆：完全二叉树，任意非叶子节点的值小于等于其子节点的值。

算法逻辑

小顶堆A和大顶堆B
A保存较大的一半（m个），长度N/2(N为偶数时)或者(N+1)/2(N为奇数时)。
B保存较小的一半（n个），长度N/2或者(N-1)/2。
insert函数：
m和n相等时向A添加，但方法是：先将元素放B中，然后B将堆顶给A。
m比n多一个时向B添加，但方法是：先将元素放A中，然后A将堆顶给B。
getMedian函数：
N为奇数时直接取A的最小值，N为偶数时取两个平均。

C++ 代码

class Solution {
public:
    priority_queue<int> maxheap;
    priority_queue<int, vector<int>, greater<int>> minheap;

    void insert(int num){
        if(minheap.size() == maxheap.size()){
            maxheap.push(num);
            auto t = maxheap.top();
            maxheap.pop();
            minheap.push(t);
        }else{
            minheap.push(num);
            auto t = minheap.top();
            minheap.pop();
            maxheap.push(t);
        }
    }

    double getMedian(){
        if(maxheap.size() == minheap.size()){
            return (minheap.top() + maxheap.top())/2.0;
        }
        else return minheap.top();

    }
};