Heap Sort

Sort given array of integers in ascending/descending order using the Heap Sort algorithm.

Heap Sort is also one of the most common sorting algorithms used in millions of applications. Heaping is a technique used in this algorithm to find the shortest number. Any new number added in heap will be heapify with O(log(n)) complexity. Heap Sort algorithm uses this heaping technique to sort elements with the best complexity. Let us see this with some examples and step-by-step illustrations.

Example:
Input: { 3, 8, 5, 10, -9, 4, -3 }
Output: { -9, -3, 3, 4, 5, 8, 10 }
Above output is the ascending sorted array

Representation of heap:

Heap is an algorithm in which all the elements in the top element is either min/max of remaining elements. Below are the formulas to represent the respective left, right, and root nodes at any point in the array. See the below illustrations to understand better.

left(n)=2*n+1 // Left node
right(n)=2*n+1 // Right node
root(n)=(n-1)/2 // Root node

There are two types of heaps, max heap and min-heap. Max heap in which root is higher than all the rest of the elements. Min heap in which root is lesser than all the rest of the elements.

Visual tree representation of input array.

As per the heap sort algorithm, the first step is to process the N/2 – 1 element in this case it is 5. So, we need to calculate the max element in the subtree {5, 4, -3} and keep it on top (as 5 is already in the top no need to change this).

Heaping on element 8. So need to calculate max element in subtree {8, 10, -9} and keep max 10 on top, as shown below.

Step2: 10 on top of the left sub-tree.

The root element is 3 now. Here we need to calculate the max element of {3, 10, 5} and keep max 10 on top, as shown below.

Step3: 10 on top of the tree.

As the top node in the left sub-tree is changed to {3}, now it is time to process the left sub-tree again. So, the max element in {3, 8, -9} is 8 so we need to keep this on top of the left sub-tree as shown below.

Max element on top of the tree.

Now it is time to do sorting on top of this array. This step swaps the top element with the last element after that process heaping on top element as it swaps with -3.

Now the array is {8, 3, 5, -3, -9, 4, 10}

Again swap top element 8 with the last element in N-1 elements array i.e, 4. Then process the heaping on swapped top, as shown below.

Now the array is {5, 3, 4, -3, -9, 8, 10}

Swap top element 5 with the last element in N-2 elements is -9. Then process the heaping on swapped top, which is as shown below.

Array is {4, 3, -9, -3, 5, 8, 10}

Do the same for all remaining steps as shown below.

Array is {3, -3, -9, 4, 5, 8, 10}
Array is {-3, -9, 3, 4, 5, 8, 10}
Now final sorted array is {-9, -3, 3, 4, 5, 8, 10}

This is how heap sort works. Now let’s jump into the coding part of the algorithm.

Heap sort “C” program

#include <iostream>

using namespace std;

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void printArray(int inp[], int len)
{
	for(int i=0; i<len; i++)
	{
		cout<<inp[i]<<" ";
	}
	cout<<endl;
}

int leftNode(int node)
{
	return 2*node + 1;
}

int rightNode(int node)
{
	return 2*node + 2;
}

void heapify(int inp[], int len, int idx)
{
	int maxIdx = idx;
	int left = leftNode(idx);
	int right = rightNode(idx);

	if(left < len && inp[left] > inp[maxIdx])
	{
		maxIdx = left;
	}
	if(right < len && inp[right] > inp[maxIdx])
	{
		maxIdx = right;
	}
	if(maxIdx != idx)
	{
		swap(inp[idx], inp[maxIdx]);
		heapify(inp, len, maxIdx);
	}
}

void heapSort(int inp[], int len)
{
	int i;
	for(i = len / 2 - 1; i >= 0; i--)
	{
		heapify(inp, len, i);
	}
	for(int i = len-1; i>=0; i--)
	{
		// Move max element at end of the array.
		swap(inp[0], inp[i]);
		// Do heapify for the reset of the array.
		heapify(inp, i, 0);
	}
}

int main(int argc, char* argv[])
{
	int inp[] = { 3, 8, 5, 10, -9, 4, -3 };
	int len = sizeof(inp) / sizeof(inp[0]);

	cout<<"Input Array is: "<<endl;
	printArray(inp, len);
	heapSort(inp, len);
	cout<<"Sorted Array: "<<endl;
	printArray(inp, len);

	return 0;
}
Output:
Input Array is: 
3 8 5 10 -9 4 -3 
Sorted Array: 
-9 -3 3 4 5 8 10

Complexity: O(n*log(n)),
Space: O(1)

If you find any errors in the algorithm or coding, please let readers know it by commenting here below. Cheers!.