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] + ” “);

}

}

}

To run the above program save this as HeapSort.java

E:\Javaprograms>javac HeapSort.java

E:\Javaprograms>java HeapSort

1 2 3 4 5 6 7 8