import java.util.Arrays;
public class HeapSort {
public static int[] arr = {3, 2, 4, 1, 6, 8, 0};
/*
* 3, 2, 4, 1, 6, 8, 0
* i/2, i * 2, i * 2 + 1
*
* 1 2 3 4 5 6 7
* 8, 6, 4, 1, 2, 3, 0
*
* N*logN
*
* 6, 2, 4, 1, 0, 3, 8
* 4, 2, 3, 1, 0, 6, 8
* 3, 2, 0, 1, 4, 6, 8
* 2, 1, 0, 3, 4, 6, 8
* 1, 0, 2, 3, 4, 6, 8
* 0, 1, 2, 3, 4, 6, 8
*
* N*logN
*
* O(NlogN)
*
* space O(1)
*/
private static void exch(int[] a, int i, int j) {
int t = a[i - 1];
a[i - 1] = a[j - 1];
a[j - 1] = t;
}
private static void sink(int[] a, int k, int N) {
while(k * 2 <= N) {
int j = 2 * k;
if(j < N && a[j - 1] < a[j]) j ++;
if(a[k - 1] > a[j - 1]) break;
exch(a, k, j);
k = j;
}
}
public static int[] sort(int[] a) {
int N = a.length;
for(int i = N/2; i >=1; i--) {
sink(a, i, N);
}
while(N > 1) {
exch(a, 1, N--);
sink(a, 1, N);
}
return a;
}
public static void main(String[] args) {
Arrays.stream(sort(arr)).forEach(System.out::println);
}
}
