public class Heapify {

    public static void heapify(int[] arr) {
        int length = arr.length;
        for (int i = (length - 1) / 2; i >= 0; i--) {
            shiftDown(arr, i);
        }
    }

    //从索引为index的位置开始进行shiftdown操作
    private static void shiftDown(int[] arr, int index) {
        int length = arr.length;
        while (2 * index + 1 < length) {
            int left = 2 * index + 1;
            int largest = left;

            if (left + 1 < length && arr[left + 1] > arr[left]) {
                largest = left + 1;
            }
            
            if (arr[index] < arr[largest]) {
                swap(arr, index, largest);
            } else { 
                break;
            }
            index = largest;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 7, 5, 4, 1, 7, 9, 8, 5, 2};
        heapify(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}