摘要：最大堆存的是到目前為止較小的那一半數(shù)，最小堆存的是到目前為止較大的那一半數(shù)，這樣中位數(shù)只有可能是堆頂或者堆頂兩個數(shù)的均值。我們將新數(shù)加入堆后，要保證兩個堆的大小之差不超過。最大堆堆頂大于新數(shù)時，說明新數(shù)將處在所有數(shù)的下半部分。

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:  [2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure. 
double findMedian() - Return the median of all elements so far. For example:
add(1) add(2) findMedian() -> 1.5 add(3)  findMedian() -> 2

時間 O(NlogN) 空間 O(N)

維護一個最大堆，一個最小堆。最大堆存的是到目前為止較小的那一半數(shù)，最小堆存的是到目前為止較大的那一半數(shù)，這樣中位數(shù)只有可能是堆頂或者堆頂兩個數(shù)的均值。而維護兩個堆的技巧在于判斷堆頂數(shù)和新來的數(shù)的大小關(guān)系，還有兩個堆的大小關(guān)系。我們將新數(shù)加入堆后，要保證兩個堆的大小之差不超過1。先判斷堆頂數(shù)和新數(shù)的大小關(guān)系，有如下三種情況：最小堆堆頂小于新數(shù)時，說明新數(shù)在所有數(shù)的上半部分。最小堆堆頂大于新數(shù)，但最大堆堆頂小于新數(shù)時，說明新數(shù)將處在最小堆堆頂或最大堆堆頂，也就是一半的位置。最大堆堆頂大于新數(shù)時，說明新數(shù)將處在所有數(shù)的下半部分。再判斷兩個堆的大小關(guān)系，如果新數(shù)不在中間，那目標堆不大于另一個堆時，將新數(shù)加入目標堆，否則將目標堆的堆頂加入另一個堆，再把新數(shù)加入目標堆。如果新數(shù)在中間，那加到大小較小的那個堆就行了（一樣大的話隨便，代碼中是加入最大堆）。這樣，每次新加進來一個數(shù)以后，如果兩個堆一樣大，則中位數(shù)是兩個堆頂?shù)木担駝t中位數(shù)是較大的那個堆的堆頂。

Java中實現(xiàn)最大堆是在初始化優(yōu)先隊列時加入一個自定義的Comparator，默認初始堆大小是11。Comparator實現(xiàn)compare方法時，用arg1 - arg0來表示大的值在前面

Leetcode

class MedianFinder {
    
    PriorityQueue maxheap;
    PriorityQueue minheap;
    
    public MedianFinder(){
        // 新建最大堆
        maxheap = new PriorityQueue(11, new Comparator(){
            public int compare(Integer i1, Integer i2){
                return i2 - i1;
            }
        });
        // 新建最小堆
        minheap = new PriorityQueue();
    }

    // Adds a number into the data structure.
    public void addNum(int num) {
        // 如果最大堆為空，或者該數(shù)小于最大堆堆頂，則加入最大堆
        if(maxheap.size() == 0 || num <= maxheap.peek()){
            // 如果最大堆大小超過最小堆，則要平衡一下
            if(maxheap.size() > minheap.size()){
                minheap.offer(maxheap.poll());
            }
            maxheap.offer(num);
        // 數(shù)字大于最小堆堆頂，加入最小堆的情況
        } else if (minheap.size() == 0 || num > minheap.peek()){
            if(minheap.size() > maxheap.size()){
                maxheap.offer(minheap.poll());
            }
            minheap.offer(num);
        // 數(shù)字在兩個堆頂之間的情況
        } else {
            if(maxheap.size() <= minheap.size()){
                maxheap.offer(num);
            } else {
                minheap.offer(num);
            }
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        // 返回大小較大的那個堆堆頂，如果大小一樣說明是偶數(shù)個，則返回堆頂均值
        if(maxheap.size() > minheap.size()){
            return maxheap.peek();
        } else if (maxheap.size() < minheap.size()){
            return minheap.peek();
        } else if (maxheap.isEmpty() && minheap.isEmpty()){
            return 0;
        } else {
            return (maxheap.peek() + minheap.peek()) / 2.0;
        }
    }
};

簡潔版

class MedianFinder {
    
    PriorityQueue maxheap = new PriorityQueue();
    PriorityQueue minheap = new PriorityQueue(Collections.reverseOrder());
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        maxheap.offer(num);
        minheap.offer(maxheap.poll());
        if(maxheap.size() < minheap.size()){
            maxheap.offer(minheap.poll());
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        return maxheap.size() == minheap.size() ? (double)(maxheap.peek() + minheap.peek()) / 2.0 : maxheap.peek();
    }
};

Lintcode

public class Solution {
    public int[] medianII(int[] nums) {
        // write your code here
        if(nums.length <= 1) return nums;
        int[] res = new int[nums.length];
        PriorityQueue minheap = new PriorityQueue();
        PriorityQueue maxheap = new PriorityQueue(11, new Comparator(){
            public int compare(Integer arg0, Integer arg1) {
                return arg1 - arg0;
            }
        });
        // 將前兩個元素先加入堆中
        minheap.offer(Math.max(nums[0], nums[1]));
        maxheap.offer(Math.min(nums[0], nums[1]));
        res[0] = res[1] = Math.min(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            int mintop = minheap.peek();
            int maxtop = maxheap.peek();
            int curr = nums[i];
            // 新數(shù)在較小的一半中
            if (curr < maxtop){
                if (maxheap.size() <= minheap.size()){
                    maxheap.offer(curr);
                } else {
                    minheap.offer(maxheap.poll());
                    maxheap.offer(curr);
                }
            // 新數(shù)在中間
            } else if (curr >= maxtop && curr <= mintop){
                if (maxheap.size() <= minheap.size()){
                    maxheap.offer(curr);
                } else {
                    minheap.offer(curr);
                }
            // 新數(shù)在較大的一半中
            } else {
                if(minheap.size() <= maxheap.size()){
                    minheap.offer(curr);
                } else {
                    maxheap.offer(minheap.poll());
                    minheap.offer(curr);
                }
            }
            if (maxheap.size() == minheap.size()){
                res[i] = (maxheap.peek() + minheap.peek()) / 2;
            } else if (maxheap.size() > minheap.size()){
                res[i] = maxheap.peek();
            } else {
                res[i] = minheap.peek();
            }
        }
        return res;
    }
}

Q：如果要求第n/10個數(shù)字該怎么做？
A：改變兩個堆的大小比例，當(dāng)求n/2即中位數(shù)時，兩個堆是一樣大的。而n/10時，說明有n/10個數(shù)小于目標數(shù)，9n/10個數(shù)大于目標數(shù)。所以我們保證最小堆是最大堆的9倍大小就行了。