private static void heapify(final Comparable[] array, final int n, final int i) {
        int root = i;
        final int left = i * 2;
        final int right = i * 2 + 1;

        if (left < n && array[left].compareTo(array[root]) < 0) {
            root = left;
        }
        if (right < n && array[right].compareTo(array[root]) < 0) {
            root = right;
        }
        if (root != i) {
            // swap
            swap(array, i, root);
            heapify(array, n, root);
        }
    }