```import java.util.Arrays;

public class HeapSortV3 {
public static int[] heap = {4, 1, 3, 2, 16,9,10,14,8,7 };

public static void main(String[] args) {
HeapSortV3 v = new HeapSortV3();
v.heapSort(heap, heap.length);
}

/**
*
* @param a
* @param i, the indict of array, begin from 0
* @param n, the heap size
*/
private void heapify(int[] a, int i, int n) {
int l = leftChild(i);
int r = leftChild(i) + 1;
int largest = -1;
if(l< n && a[l]>a[i]) {
largest = l;
}else {
largest = i;
}

if(r< n && a[r]> a[largest]) {
largest = r;
}

// if largest is not the current node, swap them, recurs to subtree
if(largest!=i) {
swap(a,largest,i);
heapify(a, largest, n);
}
}

public void buildHeap(int[] a, int n) {
// why begin from n/2?
// becuase for complete binary tree, n/2 is last non-leaf node,i.e, n/2+1,n/2+2 ...n are all leaf nodes.
for (int i = n/2; i >=0; i--) {
heapify(a, i, n);
}
}

private int leftChild(int i) {
return 2*i + 1;
}

public void heapSort(int[] a,int n) {
buildHeap(a, n);
System.out.println(Arrays.toString(a));
for (int i = n-1; i >= 1; i--) {
// swap 0 and i(n-1,n-2,...1)
swap(a, 0, i);
// remove the last element, so heap size is i(n-1,n-2,n-3...1)
heapify(a, 0, i);
}
System.out.println(Arrays.toString(a));
}

private void swap(int[] source, int dex1, int dex2) {
int temp = source[dex1];
source[dex1] = source[dex2];
source[dex2] = temp;
}
}```