数据流中的中位数

• 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
• 使用两个优先队列（分别为大根堆和小根堆）
  • 现将数数据流按大小均分为两部分，假设为min_flow, max_flow，后者个数比前者相等或者多一个（总数为奇数）
  • 大根堆：存储min_flow,这样大根堆的peek, 则为min_flow的最大值
  • 小根堆：存储max_flow,这样小根堆的peek, 则为max_flow的最小值
• 分情况讨论：
  • 数据流个数为偶数：只需去两者的peek
  • 数据流个数为偶数：取小根堆的peek
  • 每次插入操作均需对大根堆和小根堆操作，具体参考代码，较为简单
• Java代码

import java.util.*;
public class Solution {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15, (a, b) -> b-a);
    int count = 0;
    public void Insert(Integer num) {
        if(count % 2 == 0) {
            maxHeap.offer(num);
            int max = maxHeap.poll();
            minHeap.offer(max);
        } else {
            minHeap.offer(num);
            int min = minHeap.poll();
            maxHeap.offer(min);       
        }
        count++;
    }

    public Double GetMedian() {
        if(count %2 == 1) return Double.valueOf(minHeap.peek());
        else return Double.valueOf((minHeap.peek() + maxHeap.peek()))/2;
    }
}