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].

    //Start from index of n/2 since the node with index of n/2 is that last interval node with child.
    //For parent, left and right child, find the smallest to make it as parent, until the last level.
public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    public void heapify(int[] A) {
        // write your code here
        if (A == null || A.length == 0) return;
        
        for (int i = A.length / 2; i >= 0; i--) {
            shift(A, i);//后面一般的都是叶子，不需要向下移动
        }
    }
    public void shift(int[] A, int parent) {
        int left = parent * 2 + 1, right = parent * 2 + 2;
        while (left < A.length || right < A.length) {
            int left_child = left < A.length ? A[left] : Integer.MAX_VALUE;
            int right_child = right < A.length ? A[right] : Integer.MAX_VALUE;
            int index = left_child < right_child ? left : right;
            if (A[parent] < A[index]) break;
            swap(A, parent, index);
            parent = index;
            left = parent * 2 + 1;
            right = parent * 2 + 2;
        }
    }
    public void swap(int[] A, int a, int b) {
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
}