import java.util.*;
public class HeapSort {
    public static void heapSort(Integer[] array){
        buildMaxHeap(array);

        for(int i=array.length-1;i>0;i--){
            swap(array,0,i);
            maxHeapify(array,i,0);
        }
    }
    public static void buildMaxHeap(Integer[] array){
        int n=array.length;
        for(int i=n/2-1;i>=0;i--){
            maxHeapify(array,n,i);
        }
    }
    private static void maxHeapify(Integer[] array,int heapsize,int rootindex){
        int largest=rootindex;
        int leftchild=2*rootindex+1;
        int rightchild=2*rootindex+2;

        if(leftchild<heapsize && array[leftchild]>array[largest]){
            largest=leftchild;
        }
        if(rightchild<heapsize && array[rightchild]>array[largest]){
            largest=rightchild;
        }
        if(largest!=rootindex){
            swap(array,rootindex,largest);

            maxHeapify(array, heapsize, rootindex);
        }
    }
    private static void swap(Integer[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    public static void main(String args[]){
        Integer[] array={12,11,13,5,6,7};
        System.out.println("Original array:"+Arrays.toString(array));

        heapSort(array);

        System.out.println("Sorted array:"+Arrays.toString(array));
    }
}