Heapsort.java

import java.util.*;
 
public class Heapsort {
 
   public static void buildheap(int []arr) {

    for(int i=(arr.length-1)/2; i>=0; i--){
     heapify(arr,i,arr.length-1);
      }
   }
 
   public static void heapify(int[] arr, int i,int size) { 
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
       max=left;
      } else {
       max=i;
      }
 
      if(right <= size && arr[right] > arr[max]) {
       max=right;
      }
      // If max is not current node, exchange it with max of left and right child
      if(max!=i) {
         exchange(arr,i, max);
         heapify(arr, max,size);
      }
   }
 
   public static void exchange(int[] arr,int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t; 
   }
 
   public static int[] heapSort(int[] arr) {
     
      buildheap(arr);
      int sizeOfHeap=arr.length-1;
      for(int i=sizeOfHeap; i>0; i--) {
         exchange(arr,0, i);
         sizeOfHeap=sizeOfHeap-1;
         heapify(arr, 0,sizeOfHeap);
      }
      return arr;
   }
 
   public static void main(String[] args) {

        Scanner s = new Scanner (System.in);
        System.out.println("Enter number of elements");
        int n = s.nextInt();
        int a[] = new int[n];
        for (int i=0;i<n;i++) {
            a[i] = s.nextInt();
        }
      a=heapSort(a);
      System.out.println("After Heap Sort : ");
      System.out.println(Arrays.toString(a));
   }
}