public class Sorting {
 
	public static void maxHeapify (int[] A, int i) throws OutOfRangeException{
 
		int heapSize = A.length;
 
		if ((i < 0) || (i >= heapSize)){
			throw new OutOfRangeException();
		}
 
		int left = (2*i)+1;
		int right = (2*i)+2;
		int largest = i;
 
		if ((left < heapSize ) && (A > A[i])){
			largest = left;
		}
 
		if ((right < heapSize) && (A > A[i])){
			largest = right;
		}
 
		if (largest != i){
			int tmp = A[i];
			A[i] = A[largest];
			A[largest] = tmp;
		}
 
		maxHeapify(A, largest);
	}
 
 
	public static void buildHeap (int[] A){
		int n = A.length;
		int i = (int) Math.floor(n/2) - 1;
 
		try{
		while (i > 0){
			maxHeapify(A, i);
			i --;
		}
		}
		catch (OutOfRangeException ex){
			System.out.println("Error: Out of range");
		}
	}
 
	public static int deleteMax (int[] A) throws Exception{
		int heapSize = A.length;
 
		if (heapSize > 1){
			int largest = A[0];
			A[0] = A[heapSize -1];
			heapSize --;
			maxHeapify(A, 0);
			return largest;
		}
		else if (heapSize == 1){
			heapSize = 0;
			return A[0];
		}
		else{
			throw new Exception();
			//throw new EmptyHeapException();
		}
	}
 
	public static void heapSort(int [] A){
 
		int heapSize = A.length;
 
		if (heapSize > 1){
			buildHeap(A);
			int i = heapSize-1;
 
			while (i > 0){
				try{
					A[i] = deleteMax(A);
					i--;
				}
				catch (Exception ex){
					System.out.println("Heap is empty, unable to sort array.");
				}
			}
		}
	}
}