题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
由于数据是动态插入的，显然不能等所有数据输入结束后进行统一排序。
思路1
- 维护一个大顶堆和一个小顶堆，并保证如下两个特性：
1）大顶堆中的所有记录均小于小顶堆中的记录：
只要保证大顶堆顶元素始终小于小顶堆堆顶元素即可；
2）大顶堆中总记录数量较小顶堆中的总记录数量，要么大1，要么相等：
当大顶堆记录总数量较小顶堆中的总记录数量大于2时，取出大顶堆的堆顶元素插入小顶堆，此时两个堆中总记录数量相等；
当大顶堆记录总数量较小顶堆中的总记录数量小1时，取出小顶堆的堆顶元素插入大顶堆，此时大顶堆记录总数量较小顶堆中的总记录数量大1； - 如果从数据流中读出奇数个数值，那么中位数就是大顶堆的堆顶元素；如果从数据流中读出偶数个数值，那么中位数就是大顶堆的堆顶元素与小顶堆的堆顶元素的平均值；
实现手段：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();
}
};
