数据流中的中位数

用两个堆来实现

• 如果是偶数个的话，大顶堆用来存放顺序数据流左边的元素，小顶堆用来存放顺序数据流右边的元素，中位数为两个堆顶的平均数。
• 如果是奇数个的话，大顶堆存放顺序数据流+中位数，小顶堆用来存放顺序数据流右边的元素，中位数为大顶堆的堆顶。

import java.util.*;
public class Solution {

    private static PriorityQueue<Integer> maxHeap= new PriorityQueue<>((o1,o2)->(o2-o1));//左区间，用大顶堆来维护
    private static PriorityQueue<Integer> minHeap= new PriorityQueue<>(); //右区间，用小顶堆来维护
    private static int sum = 0;//用来记录数据流元素的个数(已经插入的个数）
    public static void Insert(Integer num) {
        if(sum %2 == 0) {
            maxHeap.add(num);//当两个堆里的所有元素和是偶数
        }
        else {
            minHeap.add(num);
        }
        //最大堆一定有数据，最小堆不一定有
        //当最大堆中最顶端元素大于最小堆的最顶端元素，则交换两个元素
        if(!minHeap.isEmpty() && maxHeap.peek()>minHeap.peek()) {

            int temp1 = minHeap.poll();
            int temp2 = maxHeap.poll();
            minHeap.add(temp2);
            maxHeap.add(temp1);
        }
        sum++;
    }

    public static Double GetMedian() {
        if(sum %2 == 1) {
            return (double)maxHeap.peek();
        }else {
            return (minHeap.peek() + maxHeap.peek())/2.0;
        }
    }


}