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