Heap Sort Explained

As you may know, heapsort is also one of the most asked sorting algorithms besides mergesort and quicksort and today we’re going to talk about it and I'll try my best to explain it in much simpler terms as for a beginner it can be quite complicated more so if one has less knowledge about heaps. But fear not I've got your back. So now let’s get into it.

Before moving on to heap sort you need to know about the following terminologies to properly understand the working of heapsort.

1. Heaps
2. Heap Property
3. Heapify

So let’s begin by explaining the terms stated above

1. Heaps

Heap data structure is a complete binary tree that follows the heapify property. So what’s a complete binary tee you might ask?. A complete binary tree follows these conditions.

• All nodes in every level of the tree are filled except the leaf nodes.
• The nodes are as far left as possible.

Complete Binary Tree

The heap is shown below following the heap property and this is called Max heap. It has the same root and the child nodes but there is a slight difference. The Complete Binay Tree doesn't care whether it’s root node is smaller or larger but it is of grave importance in case of the heap data structure.

Heap

2. Heap Property

While creating a heap it is essential to follow the heap property which states as follows:

• The heap where the parent node is always greater than the child nodes and provided that the root node is largest is called a Max-heap.

Max Heap

• The heap in which the child node is always greater than it’s child nodes and the root node is the smallest node is called a Min-heap.

Min heap

3. Heapify

Heapify is the process of creating a heap data structure from a binary tree. Now Heapify is the most important operation on a heap data structure as it helps to maintain the structure of the heap after several operations have been performed on the heap like(insertion, deletion). We will be using this operation a lot and it will come in handy while designing heap sort.

working of heapify is shown below

1. Select an input array.

Input array

2. Convert this array into a complete binary tree.

Complete binary tree created from the array

3. Create a heap from the binary tree.

After Heapify a max heap is created

Now that we’ve learned about all the important terms let’s start to create heap sort algorithm.

In a heap sort program, we’ll be given an unsorted array and we have to sort it. But heapsort works somewhat different than other sorting algorithms. By different, means the arrangement of each element after operations are performed. In this, the larger elements are sorted first in the last place then followed by the smaller elements, and at last, when there's one element left that element would be the smallest and the last to go in it’s sorted place.

Working of heapsort

These are the steps to be followed while implementing heapsort

1. Build a Max-heap i.e. when the root node is the largest.
2. Swap the root node with the element at the last index
3. Remove the element and reduce the size of heap by 1.
4. Heapify so that we get the largest element at the root again.
5. Repeat the above steps until all the elements are properly sorted.

Building a max heap

Before building, we need to understand two things:

• Relationship b/w a binary tree and array index.
• How to heapify a binary tree.

Relationship between the binary tree and the array index

We know that that we’ll be given an unsorted array to sort using heapsort. So this array would be converted to a binary tree with the elements at the same index. To access the child nodes there is a predefined way to do so. If a parent has index i then the index of it’s left child would be 2*i + 1 and for the right child, it would be 2*i + 2.

Binary tree and an array

How to heapify a tree

• After we have our binary tree we first heapify the tree to convert it into a max-heap data structure. We will do this using the heapify function as explained below.
• To maintain the max-heap property in a tree where both sub-trees are max-heaps, we need to run heapify on the root element repeatedly until it is larger than its children or it becomes a leaf node.

Implementation of heapify function

• In the above function, we take arr, size, and root index as the arguments for the heapify function. Then we initialize a variable called largest to keep track of our root element.
• Then we initialize the left child and the right child.
• Next, we compare the left child with the root node and same with the right child and if any of them is larger than root we store that index in the largest variable.
• Then we check if the greatest element is at the root index if not then we swap that element with the root element and continue to heapify but this time passing the largest as index.
• The reason we passed largest(which would now contain smaller element) is to check whether there is another element greater than it(as largest would be the second greatest element after root) in the depth of the heap.
• If there is such an element in the succeeding nodes of the heap we would swap that with the root element.

Heapify a tree

Now we know the importance of heapify function it is responsible for all the major operations occurring in the heap and also heap sort.

Implementation of heap sort in code

We have two functions namely sort and heapify of which we have already described what heapify does now the sort function has also a part to play.

Sort Function

The code is self-explanatory with the comments but the main point to note here are two things:

• First building a max heap in which we start our iteration from n/2–1 but why? The reason is simple as starting from this point gives us the index to the child nodes at the first level and then the subsequent child nodes until the leaf nodes.
• Second is the usage of heapsort. In this we start our iteration from n-1 to ≥0, and we swap the root (arr[0]) from the last node (arr[j]). Then we call the heapify function and pass j as the size like heapify(arr, j, 0). The real reason for this is to remove the current largest element from the tree.
• By doing this our root node will again have to be heapied and again this will happen and the size of the heap will keep on reducing by 1 as we keep on traversing until there is only one element left and all the other elements have already been sorted in their respective positions. When the last element is put into the position we get a sorted list and the loop ends.

Here’s a visual representation of the working that described above:

The working mechanism of heapsort

Working Code

You can play around with this to solidify the concept described above and I hope that now you understand heap sort and are ready to nail it. I make videos too about these topics and be sure to follow me here also.

…

So that’s it, folks. Phew!… took some time to write. So what are your thoughts please write them down in the comments.

Until next time. Bye...