public class HeapSort {

public static void main(String[] args){
    int[] arr = {49,38,65,97,76,13,27,49};
    for (int i = 0;i < arr.length;i++){
        System.out.print(arr[i] + " ");
    }
    System.out.println();
    headSort(arr);
    for (int i = 0;i < arr.length;i++){
        System.out.print(arr[i] + " ");
    }
}

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

public static void sift(int[] arr,int low,int high){
    int i = low,j = 2 * i + 1;
    int temp = arr[i];
    while (j <= high){
        if (j < high && arr[j] < arr[j + 1]){
            j++;
        }
        if (temp < arr[j]){
            arr[i] = arr[j];
            i = j;
            j = 2 * i + 1;
        }else{
            break;
        }
        arr[i] = temp;
    }
}

}