算法:数据流中的中位数

题目名称

数据流中的中位数

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

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

我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

分析

使用一个最大堆和一个最小堆;

保证:

• 最大堆和最小堆数据总数之差不超过1;
• 最大堆数值都大于最小堆数值

代码

import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

    private Queue<Integer> minHeap = new PriorityQueue<>(15);

    private Queue<Integer> maxHeap = new PriorityQueue<>(15, (x, y) -> y - x);


    // 记录总数
    int count = 0;

    public void Insert(Integer num) {
        if ((count & 1) == 0) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
        count++;
    }

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