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

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

About GSK

Hi, i am Santosh Gadagamma, a tutor in Software Engineering and an enthusiast for sharing knowledge in Computer Science and other domains. I developed this site to share knowledge to all the aspirants of technologies like, Java, C/C++, DBMS/RDBMS, Bootstrap, Big Data, Javascript, Android, Spring, Hibernate, Struts and all levels of software project design, development, deployment, and maintenance. As a programmer I believe that, "The world now needs computers to function." Hope, this site guides you as a learning tool towards greater heights. I believe that Education has no end points and i wish to learn more in the process of teaching you.

Check Also

OWASP – Open Web Application Security Project

In the world of internet the common problem is security of the application, hackers are …