最大堆，最小堆

 由于需要使用一个数据容器保存从数据流中得到的数据，那么对该容器插入数据与读取数据的时间复杂度有一定要求。  假设数据在容器中已排序，那么使用两个指针即可得到中位数，当数据量为奇数时p1,p2指向同一个数据。  如果数据量为偶数，p1指向左边最大数，p2指向右边最小数。 因此可以将数据分为两部分：

左半部分右半部分

左半部分应小于等于右半部分。由于需要快速找到左半部分的最大数与右半部分的最小数，可以想到使用最大堆与最小堆。由于要保证左右两部分数据量之差不超过1，所以可以在数据总量为偶数时将新数据插入最小堆，数据总量为奇数时将数据插入最大堆。  如果新插入最小堆的数据比最大堆的最大数据要小。因为最小堆数据要大于最大堆数据，所以需要新数据插入最大堆，将最大堆的最大数据插入最小堆。同理新插入最大堆的数据大于最小堆最小数据时，应将新数据插入最小堆，将最小堆最小数据插入最大堆。  代码如下：

class MedianFinder { private PriorityQueue<Integer> minPQ; private PriorityQueue<Integer> maxPQ; /** initialize your data structure here. */ public MedianFinder() { this.minPQ = new PriorityQueue<>(600);//初始化容量 this.maxPQ = new PriorityQueue<>(600,new Comparator<Integer>(){ public int compare(Integer o1, Integer o2) { return o2-o1; } }); } public void addNum(int num) { if(((minPQ.size() + maxPQ.size()) & 1) == 0){//数据总量为偶数，把新数据插入最小堆 if(maxPQ.size() > 0 && num < maxPQ.peek()){//最小堆的数据>最大堆数据 maxPQ.offer(num);//新数据插入最大堆 num = maxPQ.poll(); } minPQ.offer(num);//取出最大堆最大数据加入最小堆 }else{//数据总量为奇数插入最大堆 if(minPQ.size() > 0 && num > minPQ.peek()){ minPQ.offer(num); num = minPQ.poll(); } maxPQ.offer(num); } } public double findMedian() { int size = minPQ.size() + maxPQ.size(); if(size == 0) throw new RuntimeException("No numbers are available"); double median = 0; if((size & 1) == 1) median = minPQ.peek(); else median = (minPQ.peek() + maxPQ.peek())/2.0; return median; } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */