要求：如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。
思路 建立一個(gè) 小頂堆 A和 大頂堆 B ，各保存列表的一半元素，且 A 中的數(shù)據(jù)都大于 B 中的數(shù)據(jù),當(dāng)整體數(shù)目為奇數(shù)時(shí),中間的那個(gè)數(shù)就是所求.當(dāng)整體數(shù)目為偶數(shù)時(shí),中間兩個(gè)數(shù)的和再除以 2 ,就能得到結(jié)果。

class MedianFinder {
    Queue<Integer> A,B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小頂堆。保存較大的一半
        B = new PriorityQueue<>((x,y)->(y-x)); // 大頂堆，保存較小的一半
    }
    
    public void addNum(int num) {
        if(A.size()!=B.size()){
            // 從小頂堆進(jìn)去，插入到大頂堆
            A.add(num);
            B.add(A.poll());
        }else{
            // 從大頂堆進(jìn)去，插入到小頂堆
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek()         + B.peek()) / 2.0;  
    }
}