堆排序&&动态中位数

  public void heapSort(int [] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
//        for (int i = 0; i < arr.length; i++) {
//            shiftUp(arr, i);
//        }
        heapify(arr.length,arr);
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            shiftDown(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

private static void shiftUp(int [] array, int index){
    while (array[(index-1)/2] < array[index]){
        swap(array,index,(index-1)/2);
        index = (index-1)/2;
    }
}

public void shiftDown(int [] array,int index,int size){
    int left = 2*index+1;
    while (left<size){
        int largest = left+1<size  && array[left+1]>array[left] ? left+1 : left;
        largest = array[largest] > array[index] ? largest:index;
        if (largest == index){
            break;
        }
        swap(array,largest,index);
        index = largest;
        left = index * 2 +1;
    }
}


    public static void heapify(int size,int[] array){
        for (int i = (size -2)/2 ; i>=0;i--){
            shiftDown(array,i,size);
        }
    }

 private void siftdown(int[] A, int k) {
        while (k * 2 + 1 < A.length) {
            int son = k * 2 + 1;
            if (k * 2 + 2 < A.length && A[son] > A[k * 2 + 2])
                son = k * 2 + 2;
            if (A[son] >= A[k])
                break;
            
            int temp = A[son];
            A[son] = A[k];
            A[k] = temp;
            k = son;
        }
    }
    
    public void heapify(int[] A) {
        for (int i = (A.length - 1) / 2; i >= 0; i--) {
            siftdown(A, i);
        }
    }