题解 | #数据流中的中位数#

public class Solution {
    private static int[] smallHalf = new int[501];    // 存小的一半数字，用大顶堆    
    private static int[] largeHalf = new int[501];    // 存大的一半数字，用小顶堆
    
    // 如果偶数个数字，则各存一半，否则放在小数字数组
    private static int lenSmall = 0;    // 小数字部分有几个数
    private static int lenLarge = 0;    // 大数字部分有几个数
    
    public void Insert(Integer num) {
        if (lenSmall == 0) {
            smallHalf[1] = num;
            lenSmall++;
            return;
        }
        else if (lenLarge == 0) {
            if (num >= smallHalf[1]) {
                largeHalf[1] = num;
            }
            else {
                largeHalf[1] = smallHalf[1];
                smallHalf[1] = num;
            }
            lenLarge++;
            return;
        }
        else if (num < smallHalf[1]) {
            if (lenSmall == lenLarge) {
                lenSmall++;
                smallHalf[lenSmall] = num;
                swimSmall(lenSmall);
                return;
            }
            else {
                lenLarge++;
                largeHalf[lenLarge] = smallHalf[1];
                swimLarge(lenLarge);
                
                smallHalf[1] = num;
                sinkSmall(1);
                return;
            }
        }
        
        else if (num < largeHalf[1]) {
            if (lenSmall == lenLarge) {
                lenSmall++;
                smallHalf[lenSmall] = num;
                swimSmall(lenSmall);
                return;
            }
            else {
                lenLarge++;
                largeHalf[lenLarge] = num;
                swimLarge(lenLarge);
                return;
            }
        }
        
        else {
            if (lenSmall == lenLarge) {
                lenSmall++;
                smallHalf[lenSmall] = largeHalf[1];
                swimSmall(lenSmall);
                
                largeHalf[1] = num;
                sinkLarge(1);
                return;
            }
            else {
                lenLarge++;
                largeHalf[lenLarge] = num;
                swimLarge(lenLarge);
                return;
            }
        }
    }

    public Double GetMedian() {
        // 奇数个数字
        if (lenSmall > lenLarge) {
            return (double)smallHalf[1];
        }
        
        return (smallHalf[1] + largeHalf[1]) / 2.0;
    }

    private void swimSmall(int k) {
        while (k > 1) {
            if (smallHalf[k] > smallHalf[k/2]) {
                swap(smallHalf, k, k/2);
                k /= 2;
            }
            else {
                break;
            }
        }
    }
    
    private void swimLarge(int k) {
        while (k > 1) {
            if (largeHalf[k] < largeHalf[k/2]) {
                swap(largeHalf, k, k/2);
                k /= 2;
            }
            else {
                break;
            }
        }
    }
    
    private void sinkSmall(int k) {
        while (2*k <= lenSmall) {
            int t = 2 * k;
            if (t+1 <= lenSmall && smallHalf[t] < smallHalf[t+1]) {
                t++;
            }
            if (smallHalf[k] >= smallHalf[t]) {
                break;
            }
            swap(smallHalf, k, t);
            k = t;
        }
    }
    
    private void sinkLarge(int k) {
        while (2*k <= lenLarge) {
            int t = 2 * k;
            if (t+1 <= lenLarge && largeHalf[t] > largeHalf[t+1]) {
                t++;
            }
            if (largeHalf[k] <= largeHalf[t]) {
                break;
            }
            swap(largeHalf, k, t);
            k = t;
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}