Heap Sort

public class HeapSort {

	public static void main(String[] args) {
		int arr[] = {1,12,9,14,16,80,33,3,4,7,60,2};
		
		System.out.println("printing an input array ::");
		printArray(arr);
		
		heapSort(arr);
		
		System.out.println("printing the sorted array::");
		printArray(arr);
	}

	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
	
	static void heapSort(int arr[]){
		
		int n = arr.length;
		
		for(int i = n/2-1;i>=0;i--){
			heapify(arr,n,i);
		}
		
		System.out.println("printing the heapified array ::");
		printArray(arr);
		
		for(int i =n-1;i>0;i--){
			
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			
			heapify(arr,i,0);
		}
	}
	
	static void heapify(int arr[],int n	, int i){
		int largest =i;
		int left = 2*i+1;
		int right = 2*i+2;
		
		if(left<n && arr[left]>arr[largest])
			largest = left;
		if(right<n && arr[right]>arr[largest])
			largest = right;
		
		if(largest != i){
			int swap = arr[i];
			arr[i] = arr[largest];
			arr[largest] = swap;
			
			heapify(arr,n,largest);
		}
		
	}
}