Given an unlimited flow of numbers, keep track of the median of all elements seen so far.

You will have to implement the following two methods for the class

• read(int value) - read one value from the flow
• median() - return the median at any time, return null if there is no value read so far

Solution: 用max_heap维护较小一半，用min heap维护较大一半。奇数个元素时，max.size() == min.size() + 1；偶数个元素时，max.size() == min.size()。新进一个元素时，如果小于max.peek()，则加进max，否则加进min。加了后要保持两个heap size间的关系，by poll and offer

  PriorityQueue<Integer> smaller, larger;
  public Solution() {
                                     //或Collections.reverseOrder()
    smaller = new PriorityQueue<>(1, new Comparator<Integer>() {
      public int compare(Integer a, Integer b) {
        return b - a;
      }
    });
    larger = new PriorityQueue<>();
  }

  public void read(int value) {
    // write your implementation here.
    if (smaller.isEmpty() || value < smaller.peek()) {
      smaller.offer(value);
      if (smaller.size() > larger.size() + 1) {
        larger.offer(smaller.poll());
      }
    } else {
      larger.offer(value);
      if (smaller.size() < larger.size()) {
        smaller.offer(larger.poll());
      }
    }
  }

  public Double median() {
    // write your implementation here.
    int count = smaller.size() + larger.size();
    if (count == 0) {
      return null;
    } else if (count % 2 == 1) {
      return (double)smaller.peek();
    } else {
      return (smaller.peek() + larger.peek()) / 2.0;
    }
  }