题解 | #数据流中的中位数#

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

/**
* 一个大顶堆，一个小顶堆，大顶堆的堆顶小于小顶堆的堆顶元素，当N为奇数时，返回小顶堆的堆顶元素，当N为偶数时候，返回两个堆顶之和除以2。
*/
public class Solution {

    private Queue<Integer> maxHeap = new PriorityQueue<>((x, y) -> (y - x));
    private Queue<Integer> minHeap = new PriorityQueue<>();
    int size = 0;

    public void Insert(Integer num) {
    size++;
        if (size % 2 == 0) {
            if (num < minHeap.peek()) {
                maxHeap.add(num);
            } else {
                minHeap.add(num);
                Integer tmp = minHeap.poll();
                maxHeap.add(tmp);
            }
        } else {
            if (size == 1) {
                minHeap.add(num);
            } else {
                if (num < maxHeap.peek()) {
                    maxHeap.add(num);
                    minHeap.add(maxHeap.poll());
                } else {
                    minHeap.add(num);
                }
            }
        }
    }

    public Double GetMedian() {
        if (size == 0) {
            return 0.0;
        }
        if (size % 2 == 0) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return Double.valueOf(minHeap.peek());
        }
    }


}