public class heapSort {

	public static void doheapSort( Comparable [] a){
		// build heap
		for( int i=a.length/2; i>=0; i-- )
			percolateDown(a,i,a.length);
		// deleteMax
		for( int i=a.length-1; i>0; i--){
			swapRef(a,0,i);
			percolateDown(a,0,i);
		}
	}
	// swap a[i], a[j]
	private static void swapRef( Comparable [] a, int i, int j){
		Comparable tmp;
		tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	private static int leftChild( int i){
		return 2*i + 1;
	}
	// (max)heap: percolate down from position i, n is size of heap
	private static void percolateDown( Comparable [] a, int i, int n){
		int child;
		Comparable tmp;
		tmp = a[i];
		while( leftChild(i) < n ){
			child = leftChild(i);
			if( child != n-1 && a[child].compareTo(a[child+1])<0)
				child++;
			if( tmp.compareTo(a[child]) < 0)
				a[i] = a[child];
			else
				break;
			i = child;
		}
		a[i] = tmp;
	}
	public static void printHeap(Comparable [] a){
		for(int i=1; i<a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	// test heapSort
	public static void main(String [] args){
		Comparable [] array = new Comparable[10];
		array[0] = 0;
		for( int i=1; i<array.length; i++)
			array[i] = array.length-i;
		printHeap(array);
		doheapSort(array);
		printHeap(array);
	}
}