Leetcode平台上的Median of Two Sorted Arrays题目用Java堆算法实现

代码写的略恶心，明天再详查，改进一下。

这个堆其实是二叉树，用一维数组实现。

三个小小知识点：
1、java里面int的共2^32个，0当作正数处理，所以int的数据范围是(-2)^31，0，2^31-1
2、java里面switch语句，不能使用布尔值充当判断条件，如下语句是错误的：
   switch(a>b){
   case 0...
   case 1...
   }
3、Ctr + Shift + F，快速排版代码

源代码如下：

public class Solution {
    public static int[] BH; // big heap array
    public static int[] SH; // small heap array
    public static int b = 0;// BH array current length
    public static int s = 0;// SH array current length
    public static void addtoBHeap(int k) { //after an element is added into the end of the array,needs to adjust the array from bottom to root
        while(k > 0) {
            if (k % 2 == 0) { // even index
                if ((k - 2) / 2 >= 0) { //BH[k] has parent
                    if (BH[(k - 2) / 2] < BH[k]) {// parent is smaller than the son, swap them
                        int tmp = BH[k];
                        BH[k] = BH[(k - 2) / 2];
                        BH[(k - 2) / 2] = tmp;
                    }
                    k = (k - 2) / 2;
                }
            } else {//odd index
                if ((k - 1) / 2 >= 0) {//BH[k] has parent
                    if (BH[(k - 1) / 2] < BH[k]) { // parent is smaller than the son, swap them
                        int tmp = BH[k];
                        BH[k] = BH[(k - 1) / 2];
                        BH[(k - 1) / 2] = tmp;
                    }
                    k = (k - 1) / 2;
                }
            }
        }
    }
    public static void addtoSHeap(int k) {//after an element is added into the end of the array,needs to adjust the array
        while (k > 0) {
            if (k % 2 == 0) { // even index
                if ((k - 2) / 2 >= 0) {
                    if (SH[(k - 2) / 2] > SH[k]) {// parent is bigger than the son
                        int tmp = SH[k];
                        SH[k] = SH[(k - 2) / 2];
                        SH[(k - 2) / 2] = tmp;
                    }
                    k = (k - 2) / 2;
                }
            } else {
                if ((k - 1) / 2 >= 0) {
                    if (SH[(k - 1) / 2] > SH[k]) {// parent is bigger than the son
                        int tmp = SH[k];
                        SH[k] = SH[(k - 1) / 2];
                        SH[(k - 1) / 2] = tmp;
                    }
                    k = (k - 1) / 2;
                }
            }
        }
    }
    public static void adjustBHeap(int k) {//after an element is added at the root of the array,needs to adjust the array from root to bottom
        int j = 0;
        while (2 * j + 1 <= k || 2 * j + 2 <= k) { //BH[j] has son
            if (2 * j + 2 <= k) {//BH[j] has two sons
                if (BH[2 * j + 1] > BH[2 * j + 2]) {//left son is bigger
                    if (BH[j] < BH[2 * j + 1]) {// parent is smaller than son,swap them
                        int tmp = BH[j];
                        BH[j] = BH[2 * j + 1];
                        BH[2 * j + 1] = tmp;
                        j = 2 * j + 1;
                    } else
                        break;
                } else { // right son is bigger
                    if (BH[j] < BH[2 * j + 2]) {// parent is smaller than son, swap them
                        int tmp = BH[j];
                        BH[j] = BH[2 * j + 2];
                        BH[2 * j + 2] = tmp;
                        j = 2 * j + 2;
                    } else// parent is the smallest
                        break;
                }
            } else { //parent has only one left son
                if (BH[j] < BH[2 * j + 1]) {// parent is smaller than son, swap them
                    int tmp = BH[j];
                    BH[j] = BH[2 * j + 1];
                    BH[2 * j + 1] = tmp;
                    j = 2 * j + 1;
                } else//parent is the smallest
                    break;
            }
        }
    }
    public static void adjustSHeap(int k) {//after an element is added at the root of the array,needs to adjust the array from root to bottom
        int j = 0;
        while (2 * j + 1 <= k || 2 * j + 2 <= k) {//BH[j] has son
            if (2 * j + 2 <= k) {
                if (SH[2 * j + 1] < SH[2 * j + 2]) {// left son is smaller
                    if (SH[j] > SH[2 * j + 1]) {// parent is bigger than son
                        int tmp = SH[j];
                        SH[j] = SH[2 * j + 1];
                        SH[2 * j + 1] = tmp;
                        j = 2 * j + 1;
                    } else
                        break;
                } else { // right son is smaller
                    if (SH[j] > SH[2 * j + 2]) {// parent is bigger than son
                        int tmp = SH[j];
                        SH[j] = SH[2 * j + 2];
                        SH[2 * j + 2] = tmp;
                        j = 2 * j + 2;
                    } else
                        break;
                }
            } else {
                if (SH[j] > SH[2 * j + 1]) {// parent is bigger than son
                    int tmp = SH[j];
                    SH[j] = SH[2 * j + 1];
                    SH[2 * j + 1] = tmp;
                    j = 2 * j + 1;
                } else
                    break;
            }
        }
    }
    public static double findMedianSortedArrays(int[] A, int[] B) {
        int[] C = new int[A.length + B.length];
        System.arraycopy(A, 0, C, 0, A.length);
        System.arraycopy(B, 0, C, A.length, B.length);
        int l = C.length;
        int i = 0;
        double median;
        BH = new int[l];
        SH = new int[l];
        if (l > 1) {
            if (C[0] > C[1]) {
                BH[0] = C[1];
                SH[0] = C[0];
                b = 1;
                s = 1;
                i = 2;
            } else {
                BH[0] = C[0];
                SH[0] = C[1];
                b = 1;
                s = 1;
                i = 2;
            }
        } else {
            BH[0] = C[0];
            b = 1;
            i = 1;
        }
        for (; i < l; i++) {
            if (C[i] >= SH[0]) {
                if (s - b < 1) {// big data goes into the small heap if SH has
                                // no more data than BH
                    SH[s++] = C[i];
                    addtoSHeap(s - 1);
                } else { // move the root of SH to BH then insert this data into
                            // SH
                    BH[b++] = SH[0];
                    SH[0] = C[i];
                    addtoBHeap(b - 1);
                    adjustSHeap(s - 1);
                }
            }
            else if (C[i] > BH[0]) { // C[i] is between BH[0] and SH[0]
                if (b - s < 1) { // if BH is shorter than SH, insert C[i] into
                                    // BH
                    BH[b++] = C[i];
                    addtoBHeap(b - 1);
                } else {
                    SH[s++] = C[i];
                    addtoSHeap(s - 1);
                }
            }
            else {
                if (b - s < 1) {// small data goes into the big heap if BH has
                                // no more data than SH
                    BH[b++] = C[i];
                    addtoBHeap(b - 1);
                } else {// move the root of BH to SH then insert this data into
                        // BH
                    SH[s++] = BH[0];
                    BH[0] = C[i];
                    addtoSHeap(s - 1);
                    adjustBHeap(b - 1);
                }
            }
        }
        if (b == s) {
            median = ((SH[0] + BH[0]) * 0.5);
        } else if (b - s > 0) {
            median = (double) BH[0];
        } else {
            median = (double) SH[0];
        }
        return median;
    }
    public static void main(String args[]) {
        int[] A = { 1, 2, 3, 4, 6, 7, 8, 9 };
        int[] B = { 5 };
        double median;
        median = findMedianSortedArrays(A, B);
        System.out.println(median);
    }
}