LeetCode295—数据流的中位数

堆

第一次提交的代码：（堆）

class MedianFinder 
{
    Queue<Integer> maxHeap,minHeap;
    public MedianFinder()
    {
        maxHeap=new PriorityQueue<>((a,b)->b-a);//((a,b)->b-a)为转大根堆操作
        minHeap=new PriorityQueue<>();//优先队列默认小根堆
    }
    public void addNum(int num)
    {
        if(maxHeap.size()==minHeap.size()) 
        //此时默认让大根堆多一个数（即中位数）。但是考虑到num过大的情况，先把其加进小根堆，再取小根堆中最小数加入大根堆
        {
            minHeap.offer(num);//offer优先队列常用入队函数
            maxHeap.offer(minHeap.poll());//poll优先队列常用出队函数
        }
        else
        //此时情况是大根堆比小根堆多一个数。则让小根堆多一个数以保证两堆平衡，中位数只在堆顶取
        {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
    }
    public double findMedian() 
    {
       return maxHeap.size()==minHeap.size()?(maxHeap.peek()+minHeap.peek())/2.0:maxHeap.peek();
    }
}