18.9 随机生成一些数字并传入某个插入方法。 编写一个程序，高效地插入过的元素的维护中位数。

按照题意，要实现两个方法： addNewNumer(int num) 和 getMedian()

维护两个priority queue：maxHeap 和 minHeap。

maxHeap中存放小于中位数的元素，minHeap中存放大于中位数的元素。并且保证两个堆里元素数量相等或者max比min多一个。

import java.util.Comparator;
import java.util.PriorityQueue;

public class Median {

    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10, new Comparator<Integer>() {
        public int compare(Integer x, Integer y) {
            return y.compareTo(x);
        }
    });
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

    public void addNewNumber(int num) {
        if (maxHeap.size() == minHeap.size()) {
            if (!minHeap.isEmpty() && num > minHeap.peek()) {
                maxHeap.add(minHeap.remove());
                minHeap.add(num);
            } else {
                maxHeap.add(num);
            }

        } else {
            if (num < maxHeap.peek()) {
                minHeap.add(maxHeap.remove());
                maxHeap.add(num);
            } else {
                minHeap.offer(num);
            }

        }

    }

    public double getMedian() {
        if (maxHeap.isEmpty())
            return 0;
        if (maxHeap.size() == minHeap.size())
            return (double) (minHeap.peek() + maxHeap.peek()) / 2;
        else
            return maxHeap.peek();

    }

    public static void main(String[] args) {
        Median m = new Median();
        m.addNewNumber(1);
        System.out.println(m.getMedian());

        m.addNewNumber(3);
        System.out.println(m.getMedian());

        m.addNewNumber(4);
        System.out.println(m.getMedian());

        m.addNewNumber(5);
        System.out.println(m.getMedian());

        m.addNewNumber(2);
        System.out.println(m.getMedian());

    }

}