public class HeapSort {

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};

        System.out.println("Before: " + Arrays.toString(array));
        sort(array);
        System.out.println("After:  " + Arrays.toString(array));
    }

    public static void sort(int[] arr) {

        // i is the size of the sub array to be heapified
        for (int i = arr.length; i > 0; i--) {

            // Heapify sub array arr[0:i-1], after this procession, the largest value
            // will be at the first slot of the array.
            maxHeapify(arr, i);

            // swap the first value, also know as the max value of sub array arr[0:i-1]
            // to the end of the array.
            swap(arr, 0, i - 1);
        }
    }

    private static void maxHeapify(int[] arr, int size) {
        int parentIdx = size / 2;

        for (; parentIdx >= 0; parentIdx--) {

            // parentIdx can't be th leaf node.
            if (parentIdx * 2 >= size) {
                continue;
            }

            // left child node
            int left = parentIdx * 2;

            // right child node, assign the left node to it if right child not exits.
            int right = (left + 1) >= size ? left : (left + 1);

            int maxChildId = arr[left] >= arr[right] ? left : right;

            // swap the max child to parent if the max is larger than parent
            if (arr[maxChildId] > arr[parentIdx]) {
                swap(arr, maxChildId, parentIdx);
            }
        }
    }

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