【剑指 offer】数据流中的中位数

1、题目描述

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

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

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

样例

输入：1, 2, 3, 4
输出：1,1.5,2,2.5

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

2、问题描述：

3、问题关键：

• 用一个大根堆，一个小根堆，大根堆保存较小的值，小根堆保存较大值。
• 如果两个堆保存的数量相同，那么两个堆顶元素的平均值就是中位数。
• 数据进来的时候，直接放入大根堆中，如果大根堆的数据量比小根堆多2，那么就将大根堆堆顶元素放入小根堆。
• 如果小根堆的堆顶元素小于大根堆堆顶元素，那么将小根堆堆顶元素和小根堆堆顶元素交换，保证小根堆元素大于等于大根堆元素。

4、C++代码：

class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    void insert(int num){
        max_heap.push(num);
        if (min_heap.size()) {
            int tmp = min_heap.top();
            if (tmp < max_heap.top()) {//如果小根堆堆顶元素小于大根堆，那么就交换堆顶元素。保证小根堆元素大于大根堆元素。
                min_heap.pop();
                min_heap.push(max_heap.top());
                max_heap.pop();
                max_heap.push(tmp);
            }
        }
        if (max_heap.size() > min_heap.size() + 1) {//如果大根堆元素比小根堆元素大2，那么将堆顶元素放入小根堆。
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }
    double getMedian(){//数量量相同那么就是堆顶元素平均数，否则是大根堆堆顶元素为中位数。
        if (min_heap.size() == max_heap.size() && min_heap.size()) 
            return (min_heap.top() + max_heap.top()) / 2.0;
        else 
            return max_heap.top();
    }
};