Data Structures and Algorithms

Heap Sort Explained with C++ implementation

A Comprehensive guide to Heap Sort Algorithm

5 min readApr 18, 2020

Hello World !!

Welcome to my first blog on medium. I have tried my best to explain the key concepts in detail. I have also added C++ code implementation of Heap Sort. Trust me you’ll learn a lot after going through this article.

Enjoy the ride !!

In computer science, heapsort is a comparison-based sorting algorithm. Before diving deep into the Heap Sort explanation first we’ll learn about array representation of the binary tree.

Note: Array index will start from 1 for ease of explanation.

Array representation of a complete binary tree

If a node is present at index: i
Node’s left child will be present at index: 2 * i
Node’s right child will be present at index: ( 2 * i ) + 1
And Node’s parent is at index: floor( i/2 )

Now you might be wondering about complete binary tree !!
According to Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Another definition using array representation:

If you represent a binary tree in an array then there should not be any empty locations or gap in between the elements ( from 1st element to the last element )

Have a look at these diagrams:

Some facts:

A Binary Tree with a maximum number of nodes is a Full Binary Tree.
Every Full Binary Tree is also a Complete Binary Tree.
A Complete Binary Tree is already a Full Binary Tree up to height h-1.
Height of a Complete Binary Tree will always be minimum i.e. log(n) because unnecessary we are not going to the next level unless one of the level is completely filled.

Heap is a Complete Binary Tree

Let’s talk about different versions of the heap:

Max Heap

In Max heap, every node is having the value greater than or equal to all its descendants.
The root will have the maximum value.

Min Heap

In Min Heap, every node is having the element smaller than or equal to all it’s descendants.
The root will have the minimum value.

The procedure of heap sort consists of two steps:

For a given set of numbers,

Create a heap.
Delete all the elements from the heap.

Creating a heap ( A siftUp approach)

We don’t need an extra array for heap creation. Within an array, we can form the heap.

So that’s why it is called as In-Place creation.

Time is equal to the number of swaps. The maximum number of swaps depends on the height of complete binary tree i.e. O( log(n) ).

So for n elements insertion, total time taken is O(nlog(n)).

Complete binary tree height ranges from O(1) to O( log(n) ).

As you can see element moves from leaf towards the root.

The direction of adjustment is upwards.

Deleting from heap

Always root element gets deleted from the heap. Other elements deletion will disturb the complete binary tree property.

Last leaf node replaces the root element.

As you can see element moves from root to leaf.

The direction of adjustment is downwards.

So for deleting n elements one by one, total time taken is O(nlog(n)).

Total time taken for heap sort is O(nlogn)

Let’s Code Heap Sort in C++

Heapify ( A siftDown approach)

A faster method for creating a heap

Total time taken for heapify is O(n)

Heapify is a siftDown approach. Time is less because the total work done is less.

Let’s Code Heapify function in C++

Summary:

Heap Sort is a sum of two stages:

O(n) time complexity for heap creation ( using heapify )
O(nlog(n)) time complexity for deletion of nodes one by one

Total time taken :
n + nlog(n) = O(nlog(n))

Resources

I referred the following resources for my understanding and found it very useful. Have a look at these awesome resources if you’re interested in learning more about heap sort.