Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Solution: 从k = A.length/2-1开始，比较A[k]与A[2k+1], A[2k+2], k--

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