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;
}
}
}
