3.数据流的中位数

• 3.17

• 先加左边

• 不用判断是否左边大于右边，因为左边一定大于右边，要一直保持左至少等于右边（左边可以多）

• 返回时如果是左边多，则返回左边最大的

• 2.17

  • 先加个左边，在给右边，再平衡
  • 给出中位数（看是不是左边多一个）

• 2.3

class MedianFinder {
    // 左边的堆：存较小的一半 -> 需要最大值 -> 大顶堆
    private PriorityQueue<Integer> leftHeap;
    // 右边的堆：存较大的一半 -> 需要最小值 -> 小顶堆
    private PriorityQueue<Integer> rightHeap;
 
    public MedianFinder() {
        leftHeap = new PriorityQueue<>((a, b) -> b - a); // 降序
        rightHeap = new PriorityQueue<>();               // 升序
    }
    
    public void addNum(int num) {
        // 先往左边放，选个老大哥出来
        leftHeap.offer(num);
        // 把左边的老大哥扔到右边去当小弟
        rightHeap.offer(leftHeap.poll());
        
        // 平衡：规定左边可以比右边多 1 个，但不能少
        if (leftHeap.size() < rightHeap.size()) {
            leftHeap.offer(rightHeap.poll());
        }
    }
 
	public double findMedian() {
	        if(leftHeap.size()>rightHeap.size()){
	            return leftHeap.peek();
	        }else{
	            return (leftHeap.peek()+rightHeap.peek())/2.0;
	        }
	    }
    }

// ...

}