Java Code House

The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input array A[1 : : n ],where n=A:length. Since the maximum element of the array is stored at the root A[1] , we can put it into its correct final osition by exchanging it with A[n] . If we now discard node n from the heap - and we can do so by simply decrementing A:heap-size-- we observe that the children of the root remain max-heaps, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property, however, is call MAX-HEAPIFY(A, 1), which leaves a max-heap in A[1 : : n -1] . The heapsort algorithm then repeats this process for the max-heap of size n- 1 down to a heap of size 2.
     The program written below has build_max_heap() to build the max-heap, max_heapify() to retain the max-heap property and heap_sort() for sorting. The most important thing of the code is that you can use this to sort anything. Just pass an array of any object which is comparable i.e. implements Comparable interface or any array of wrapper class objects like Integer, Float etc. This is only beacause we have done this using Java's generics feature to make this code generic and general and no need for different implementations.

Heapsort operation

--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------

import java.util.Scanner;

/*This code can take in any array of Comparable i.e whose data can be compared and generates the sorted elements using heap sort*/
public class HeapSort<E extends Comparable<? super E>>{
    private int heap_size;
private E A[];

public HeapSort(E a[]){
  A=a;
}

private void build_max_heap(){  //building max-heap
   heap_size=A.length-1;
   for(int i=heap_size/2;i>=0;i--)
  max_heapify(i);
}

private void swap(int i,int j){
   E tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}

private void max_heapify(int i){
   int l=2*i,r=2*i+1;  //left and right child
int largest;
   if(l<=heap_size && A[l].compareTo(A[i])>0)
  largest=l;
else largest=i;
if(r<=heap_size && A[r].compareTo(A[largest])>0)
  largest=r;
if(largest!=i){    //finding largest, swapping and then reheapify
  swap(i,largest);
  max_heapify(largest);
}
}

public E[] heap_sort(){
   build_max_heap();
for(int i=A.length-1;i>=0;i--){
  swap(0,i);  //swapping with first
  heap_size--;  //decreasing size
  max_heapify(0);  //reheapify
}

return A;
}

public static void main(String[] args)throws Exception{
Scanner sc=new Scanner(System.in);
System.out.print("Enter size : ");
int n=sc.nextInt();
Integer a[]=new Integer[n];
System.out.println("Enter elements to be sorted -->");
for(int i=0;i<n;i++)
  a[i]=sc.nextInt();
  
HeapSort<Integer> obj=new HeapSort<Integer>(a);
a=obj.heap_sort();
System.out.println("Sorted array -->");
for(int i=0;i<n;i++)
  System.out.print(a[i]+"  ");
    }
}