摘要：最大堆存的是到目前為止較小的那一半數(shù)，最小堆存的是到目前為止較大的那一半數(shù)，這樣中位數(shù)只有可能是堆頂或者堆頂兩個(gè)數(shù)的均值。我們將新數(shù)加入堆后，要保證兩個(gè)堆的大小之差不超過。最大堆堆頂大于新數(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

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

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

Java中實(shí)現(xiàn)最大堆是在初始化優(yōu)先隊(duì)列時(shí)加入一個(gè)自定義的Comparator，默認(rèn)初始堆大小是11。Comparator實(shí)現(xiàn)compare方法時(shí)，用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ù)字在兩個(gè)堆頂之間的情況
        } else {
            if(maxheap.size() <= minheap.size()){
                maxheap.offer(num);
            } else {
                minheap.offer(num);
            }
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        // 返回大小較大的那個(gè)堆堆頂，如果大小一樣說明是偶數(shù)個(gè)，則返回堆頂均值
        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;
            }
        });
        // 將前兩個(gè)元素先加入堆中
        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個(gè)數(shù)字該怎么做？
A：改變兩個(gè)堆的大小比例，當(dāng)求n/2即中位數(shù)時(shí)，兩個(gè)堆是一樣大的。而n/10時(shí)，說明有n/10個(gè)數(shù)小于目標(biāo)數(shù)，9n/10個(gè)數(shù)大于目標(biāo)數(shù)。所以我們保證最小堆是最大堆的9倍大小就行了。