Heap Sort Algorithm

There are a numerous sorting algorithms. Among them Heap Sort is one which has a consistent complexity for any input. For any of worst-case, best-case, reverse order heap sort has O(nlogn) runtime which is considerably best complexity for sorting.

To perform heap sorting, the given array is first constructed into heap. Heap is a tree-based data structure where there is a relation for all parent-child nodes. There are two heaps namely “max heap” and “min heap”. In max heap, parent node has a value greater than its children nodes. Similarly, in min heap, parent node has a value lesser than its children nodes.

For heap sorting we use complete binary max-heap which mean the heap data structure is a complete binary tree.

Let us here construct the required heap in an array instead of making a tree. For constructing a heap, for every new element we take in, we need to compare it with a set of already existing elements in the array. Let us first look its function.

#define swapAB(a,b) a=a+b-(b=a)

void heapify(int a[],int heap[],int n)
{
    int i = 1,temp;
    heap[0] = a[0];
    for(;i < n;++i)
    {
		heap[i] = a[i];
		temp = i;
		while(heap[(temp-1)/2] < heap[temp])
		{
			swapAB(heap[(temp-1)/2],heap[temp]);
			temp = (temp-1)/2;
		}
	}
}

Let a[] is the input array for which heap is to be constructed. heap[] will be initially empty and consists pre-order traversal of heap tree after execution of this function. n is number of elements in input array. In the construction, each new element that is entering heap[] is compared to its immediate parent node. If value of parent node is less than current node, values are swapped and current node is shifted to parent node. The process is continued until the swapping takes place( or till parent node has greater value than child node) or till it reaches root node. Parent node of heap[i] would be heap[(i-1)/2] as we follow 0-based indexing.

If you now see the heap, we could notice that root node(heap[0]) is the maximum value of the array. In sorting the inputs, we take this fact and swap first index with last index and omit the last index in further calculations as we gave the last position to largest number. We need to make sure that remaining heap, has the heap conditions satisfied i.e. root node value is greater than children node values. As we changed only one node in remaining heap, i.e. heap[0], we need to start checking only for that node till it reaches to its correct position.

Heap sort implementation in C++.

#include <bits/stdc++.h>

using namespace std;

#define swapAB(a,b) a=a+b-(b=a)

void printA(int a[],int n) //prints array
{
	int i = 0;
	while(i < n)
		cout<<a[i++]<<" ";
	cout<<endl;
}

void heapify(int a[],int heap[],int n)  //constructs heap
{
    int i = 1,temp;
    heap[0] = a[0];
    for(;i < n;++i)
    {
		heap[i] = a[i];
		temp = i;
		while(heap[(temp-1)/2] < heap[temp])
		{
			swapAB(heap[(temp-1)/2],heap[temp]);
			temp = (temp-1)/2;
		}
	}
}

void heapsort(int heap[],int n)
{
	int temp,m;
	while(n!=1)
	{
		swapAB(heap[0],heap[n-1]);
		n=n-1;
		temp = 0;
        while(1)
        {
			if((2*temp + 2) < n)
			{
				m = max(heap[2*temp + 1],heap[2*temp + 2]);
				if(heap[temp] < m)
				{
                    if(heap[2*temp + 1] == m)
					{
						swapAB(heap[temp],heap[2*temp + 1]);
						temp = 2*temp + 1;
					}
					else
					{
						swapAB(heap[temp],heap[2*temp + 2]);
						temp = 2*temp + 2;
					}
				}
				else goto endwhile;
			}
			else if(2*temp + 1 < n)
			{
				if(heap[temp] < heap[2*temp + 1])
				{
					swapAB(heap[temp],heap[2*temp + 1]);
					temp = 2*temp + 1;
				}
				else goto endwhile;
			}
			else
				break;
        }
        endwhile: {}
	}
}

int main()
{
    int n;
    cout<<"No. of elements in Array : ";
    scanf("%d",&n);
    int i = 0;
    int a[n],heap[n];
    cout<<"Enter elements : ";
    for(;i < n;++i)
		scanf("%d",&a[i]);
    heapify(a,heap,n);
    cout<<"Heap : ";
    printA(heap,n);  //prints array
    heapsort(heap,n);
    cout<<"Sorted Array : ";
    printA(heap,n);
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s