Heap sort algorithm

Heap sort algorithm

Heap sort was invented by John Williams. Heap is a complete binary tree in which every parent node be either greater or lesser than its child nodes.

Heap sort is a comparison based sorting technique based on Binary Heap data structure.
It is similar to selection sort where we first find the maximum element and place the maximum element at the end.
We repeat the same process for remaining element.

Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case running time. Heap sort involves building a Heap data structure from the given array and then utilizing the Heap to sort the array.

How Heap Sort Works?

Heap sort algorithm is divided into two basic parts:

Creating a Heap of the unsorted list/array.
Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal.

Initially on receiving an unsorted list, the first step in heap sort is to create a Heap data structure(Max-Heap or Min-Heap). Once heap is built, the first element of the Heap is either largest or smallest(depending upon Max-Heap or Min-Heap), so we put the first element of the heap in our 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.

Heap sort complete example and process

Since the tree satisfies Max-Heap property, then the largest item is stored at the root node.
Remove the root element and put at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place.
Reduce the size of the heap by 1 and heapify the root element again so that we have highest element at root.
The process is repeated until all the items of the list is sorted.

Complexity Analysis of Heap Sort

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 not a Stable sort, and requires a constant space for sorting a list.
Heap Sort is very fast and is widely used for sorting

Algorithm of Heap sort

HEAPSORT (A, N):

An array A with N elements is given.
This algorithm sorts the element of A.

[Build a heap A ,using a procedure 1]
Repeat for J=1 to N-1
Call INSHEAP(A, J, A[J+1])
[sort A by repeatedly deleting the root of H, using procedure 2]
Repeat while N>1:
Call DELHEAP(A , N,VALUE)
Set A[n+1]:=value
Exit

C Program example of Heap Sort

#include<stdio.h>

void create(int []);
void down_adjust(int [],int);

int main()
{
	int heap[30],n,i,last,temp;

	printf("Enter no. of elements:");
	scanf("%d",&n);

	printf("\nEnter elements:");
	for(i=1;i<=n;i++)
		scanf("%d",&heap[i]);

	//create a heap
	heap[0]=n;
	create(heap);

	//sorting
	while(heap[0] > 1)
	{
		//swap heap[1] and heap[last]
		last=heap[0];
		temp=heap[1];
		heap[1]=heap[last];
		heap[last]=temp;
		heap[0]--;
		down_adjust(heap,1);
	}

	//print sorted data
	printf("\nArray after sorting:\n");
	for(i=1;i<=n;i++)
		printf("%d ",heap[i]);

	return 0;
}

void create(int heap[])
{
	int i,n;
	n=heap[0]; //no. of elements

	for(i=n/2;i>=1;i--)
		down_adjust(heap,i);
}

void down_adjust(int heap[],int i)
{
	int j,temp,n,flag=1;
	n=heap[0];

	while(2*i<=n && flag==1)
	{
		j=2*i;    //j points to left child
		if(j+1<=n && heap[j+1] > heap[j])
			j=j+1;
		if(heap[i] > heap[j])
			flag=0;
		else
		{
			temp=heap[i];
			heap[i]=heap[j];
			heap[j]=temp;
			i=j;
		}
	}
}

Output

    Enter no. of elements:5
    Enter elements:12 8 46 3 7
    Array after sorting:
    7 8 12 23 46

Heap sort algorithm

How Heap Sort Works?

Heap sort complete example and process

Complexity Analysis of Heap Sort

Algorithm of Heap sort

Posts to Review: