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();
}
};
