/**
 * Implements Heapsort for an array of int's starting at index 0 
 * @author Dominik Gruntz
 */

class HeapSort {
	/**
	 * Internal method for Heapsort
	 * @param i the index of an item in the heap
	 * @return the index of the left child
	 */
	private static int leftChild( int i) {
		// 2 (i+1) - 1
		return 2*i + 1;
	}

	/**
	 * Internal method to percolate down in the max-heap.
	 * @param heap an array of int's
	 * @param hole index of the element which is percolated
	 * @param n the logical size of the binary heap
	 */
	private static void percDown(int[] heap, int hole, int size) {		
		int tmp = heap[hole];
		
		while (leftChild(hole) < size) {
			int child = leftChild(hole);
			if (child < size-1 && heap[child+1] > heap[child]) {
				child++;
			}
			if (heap[child] > tmp) {
				heap[hole] = heap[child];
				hole = child;	
			} 
			else 
				break;
		}
		heap[hole] = tmp;
	}

	/**
	 * Sort the array with Heapsort
	 * @param a zero indexed array with ints that are to be sorted
	 * @param size first size elements in array a are sorted
	 */
	static void sort(int[] a, int size)	{
		int i;
		int tmp;
		
		/* Build Heap in O(n) */
		for( i = size / 2 - 1; i >= 0; i--)
			percDown( a, i, size);
		
		for( i = size-1; i > 0; i--) {
			/* deleteMax: swapReference then percolate down */
			tmp  = a[i];
			a[i] = a[0];
			a[0] = tmp;
			percDown( a, 0, i);		
		}	 
	}
}