题目：
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
分析：
我们可以想象出一个排序数组的中位数可以将数组分成两部分，那么我们利用最大堆和最小堆来分别存储这两部分，且如果要求中位数时，可以通过直接返回堆顶元素，在O(1)的时间内求解。
要保证最大堆的所有元素小于等于最小堆的元素，在插入元素的时候通过已插入数字数目来判断：
如果插入数目是偶数，就将元素插入最大堆，然后再将最大堆中堆顶元素取出，插入最小堆中。
如果插入数目是奇数，就将元素插入最小堆，然后再将最小堆中堆顶元素取出，插入最大堆中。
这样做就可以保证最大堆的所有元素小于等于最小堆的元素。
然后如果数目是奇数时，中位数等于最小堆的堆顶元素，为偶数时，中位数等于最小堆和最大堆的堆顶元素的平均值。
以[5,2,3,4,1,6,7,0,8]为例：
| 插入元素 | 最小堆 | 最大堆 | 中位数 |
| 5 | [5] | [] | 5 |
| 2 | [5] | [2] | 3.5 |
| 3 | [3,5] | [2] | 3 |
| 4 | [4,5] | [3,2] | 3.5 |
| 1 | [3,4,5] | [2,1] | 3 |
| 6 | [4,5,6] | [3,2,1] | 3.5 |
| 7 | [4,5,6,7] | [3,2,1] | 4 |
| 0 | [4,5,6,7] | [3,2,1,0] | 3.5 |
| 8 | [4,5,6,7,8] | [3,2,1,0] | 4 |
程序：
C++
class Solution {
public:
void Insert(int num)
{
if(c % == ){
maxHeap.push(num);
minHeap.push(maxHeap.top());
maxHeap.pop();
}
else{
minHeap.push(num);
maxHeap.push(minHeap.top());
minHeap.pop();
}
c++;
}
double GetMedian()
{
if(c % == ){
return (double)(maxHeap.top() + minHeap.top()) / ;
}
else{
return (double)minHeap.top();
}
}
private:
priority_queue<int, vector<int>, less<int> > maxHeap;
priority_queue<int, vector<int>, greater<int> > minHeap;
int c = ;
};Java
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution { public void Insert(Integer num) {
if(count % 2 == 0){
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
}else{
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
count++;
} public Double GetMedian() {
if(count % 2 == 0){
return new Double(minHeap.peek() + maxHeap.peek()) / 2;
}else{
return new Double(minHeap.peek());
}
}
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
private int count = 0; }