Heap Sort

It is like a comparison based sorting, it is the improvement
of selection sort. Heap sort is divide the elements into two regions sorted and
unsorted, and it iteratively shrinks the unsorted region by extracting the
largest elements and moving those into sorted region. 

Heap Sort was invented by J W J Williams in 1964.

Heap : A sorting algorithm that works by first organizing
the data to be sorted into a special type of binary tree called heap.  The heap itself consists of largest element
at the top position of the tree. 

Working of Heap sorting: In the first step receiving an un
sorted list and it create a Heap data structure (Max, Min heap). Once
successfully built the heap, the first element of the heap may be either
largest or smallest it depends on Max or Min heap, so put this heap into an
array. Then we again make heap using the remaining elements, to again pick the
first element of the heap and put it into the array. We keep on doing the same
repeatedly until we have the complete sorted list in our array.

Worst Case Time Complexity : O(n log n)

Best Case Time Complexity : O(n log n)

Average Time Complexity : O(n log n)

Space Complexity : O(1)

Heap sort is widely used sorting, and
it requires a constant space for sorting a list. It is a not stable sort.

 See the below example program in Java: 

public class HeapSort
{
    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;

   
    public static void buildheap(int []a){
        n=a.length-1;
        for(int i=n/2;i>=0;i--){
            maxheap(a,i);
        }
    }
   
    public static void maxheap(int[] a, int i){
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
       
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            exchange(i,largest);
            maxheap(a, largest);
        }
    }
   
    public static void exchange(int i, int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
        }
   
    public static void sort(int []a0){
        a=a0;
        buildheap(a);
       
        for(int i=n;i>0;i--){
            exchange(0, i);
            n=n-1;
            maxheap(a, 0);
        }
    }
   
    public static void main(String[] args) {
        int []a1={6, 5, 3, 1, 8, 7, 2, 4};
        sort(a1);
        for(int i=0;i<a1.length;i++){
            System.out.print(a1[i] + " ");
        }
    }
}

Output of the above program :

E:\Javaprograms>javac HeapSort.java

E:\Javaprograms>java HeapSort
1 2 3 4 5 6 7 8

 See the graphical representation of Heap sort for the above program: