Interview Kickstart has enabled over 3500 engineers to uplevel.
Whether it is for the software developer, coding engineer, software engineer, or any such position in the IT industry, heap sort is an essential part of the technical interview prep. It’s almost as if its primary use is cracking job interviews! It is rarely used in real-world scenarios, despite being one of the most interesting sorting algorithms.
Having trained over 13,500 software engineers, we know what it takes to crack the toughest tech interviews. Our alums consistently land offers from FAANG+ companies. The highest-ever offer received by an IK alum is a whopping $1.267 Million!
At IK, you get the unique opportunity to learn from expert instructors who are hiring managers and tech leads at Google, Facebook, Apple, and other top Silicon Valley tech companies.
Want to nail your next tech interview? Sign up for our FREE Webinar.
This article will discuss the following:
To understand how heap sort works, we first need to understand some basic concepts related to binary heaps. Feel free to skip them if you are already familiar with these concepts.
Heap is a tree-based data structure in which all the tree nodes are in a particular order, such that the tree satisfies the heap properties (that is, a specific parent-child relationship is followed throughout the tree).
A heap data structure where the tree is a complete binary tree is referred to as a binary heap.
A complete binary tree is a binary tree in which:
A full binary tree is a binary tree where every node has 0 or 2 children.
1. They are complete binary trees: This means all levels are totally filled (except maybe the last level), and the nodes in the last level are as left as possible. This property makes arrays a suitable data structure for storing binary heaps.
We can easily calculate the indices of a node’s children. So, for parent index i, the left child will be found at index 2*i+1, and the right child will be found at index 2*i+2 (for indices that start with 0). Similarly, for a child at index i, its parent can be found at index floor((i-1)/2).
2. Heaps are mainly of two types — max heap and min heap:
3. Root element: In a max heap, the element at the root will always be the maximum. In a min heap, the root element will always be the smallest. The heap sort algorithm takes advantage of this property to sort an array using heaps.
Heap sort is an efficient comparison-based sorting algorithm that:
Before going into the workings of heap sort, we’ll visualize the array as a complete binary tree. Next, we turn it into a max heap using a process called heapification.
The brilliance of heapification lies in the following fact:
If all the subtrees in a binary tree are MaxHeaps themselves, the whole tree is a MaxHeap.
One way to implement this idea would be:
If we successfully do that, we will have transformed the whole binary tree into a valid MaxHeap after processing all the nodes.
One way to optimize this process is by ignoring all the leaf nodes since they don't have any children:
This journey ends when we eventually reach the topmost node and process it.
Let’s see this in more detail:
If this sounds like a recursive method, that's because it is! We keep calling this method recursively for the child nodes that got updated until we reach a stage where the child node is either a leaf or has children, each of whose values are lower.
You might have wondered why we decided to traverse bottom to top and not top to bottom. That's because steps 1-3 for heapifying a node work only if the child nodes are heapified already.
Max/Min heap formation:
At the end of this process, a max heap is fully formed. We can also make a min heap simply by changing the condition to “parent value should be <= each of its children’s values” (swap values if the condition isn’t met).
Look at the following example:
But even when sorting is not the aim, a min/max heap in itself is a useful construction:
This quality of heaps can come in handy when we want to extract only the largest or smallest element from an array without sorting the remaining elements.
Heap sort has limited usage since algorithms like merge sort and quicksort are better in practice. We extensively use heaps for problems like getting the largest or smallest elements in an array, sorting an almost sorted array, etc.
Some key applications of Heap sort include:
Now that we’ve learned how to create a heap from an array using the heapify method, we will look into using the heap to sort the array.
After the heap formation using the heapify method, the sorting is done by:
This process can be best illustrated using an example:
The process above ends when heap size = 2 because a two-element heap is always considered sorted.
So basically, the heap sort algorithm has two parts that run recursively till heap size >= 2:
Here’s the algorithm for heap sort:
Step 1: Build Heap. Build a heap from the input data. Build a max heap to sort in increasing order, and build a min heap to sort in decreasing order.
Step 2: Swap Root. Swap the root element with the last item of the heap.
Step 3: Reduce Heap Size. Reduce the heap size by 1.
Step 4: Re-Heapify. Heapify the remaining elements into a heap of the new heap size by calling heapify on the root node.
Step 5: Call Recursively. Repeat steps 2,3,4 as long as the heap size is greater than 2.
Each time, the last array position is discarded from the heap once it contains the correct element. The process is repeated until all the input array elements are sorted. This happens when the heap size is reduced to 2 since the first two elements will automatically be in order for a heap that satisfies the heap property.
Following is the pseudocode for heap sort. Please look and try to implement this in a programming language of your choice.
We have implemented the heap sort algorithm to sort in ascending order in C++:
The Heap Sort Program
The time complexity of heap sort is non-quadratic and comes out the same in the best, worst and average cases:
Let’s see how.
(Note: The following sections are based on working with MaxHeaps)
The heapify method is run on a node whose child nodes are already heapified.
The time complexity for calling the heapify method for all the tree nodes (from bottom to top):
This step involves swapping the left-most value in the array with the right-most value in the array occupied by the heap and reheapification of the new smaller heap.
We will perform this extraction N times, so the total time complexity of getting a sorted array out of a MaxHeap is O(N*log(N)).
We can calculate the total time complexity of heap sort as:
Time for creating a MaxHeap + Time for getting a sorted array out of a MaxHeap
=O(N) + O(Nlog(N))
Heap sort’s space complexity is a constant O(1) due to its auxiliary storage.
Question 1: Does the heap data structure have to be binary-tree-based?
No, a heap does not always need to be a binary tree. But in heap sort, we use arrays to represent the heap. Using the array, we can easily calculate and track the relationship between a parent index, its left child index, and the right child index for a binary heap. And a binary heap has to be binary-tree-based.
Question 2: Can heap sort be made stable?
While heap sort is typically not stable, it can be made stable by considering the position of the elements with the same value. During heapification, treat the element towards the right as greater than the element towards the left, and your sorting will be stable.
Question 3: Why are arrays used to visualize and implement binary heaps?
Storing and accessing values in an array is faster and less complicated than using a more complex data structure. One of the main advantages of using more complex data structures is the use of methods provided by the standard library for common operations related to the data structure, e.g., push() and pop() methods for a stack.
However, storing a complete binary tree in an array still allows us to perform all operations relevant to the tree with much ease. We can find the left child, right child, parent node, root, and the last element of a tree with basic arithmetic operations on the index of the current node or the variable maintaining the size of the tree.
Question 4: How much time does it take to find the maximum and minimum element in a max heap?
The maximum element is present at the root and can be found in O(1) time. The minimum element will be present in the leaf nodes, and all leaf nodes have to be checked to find the minimum element. Hence, the minimum element can be found in O(n) time.
Question 5: What is heap sort’s space complexity and why?
Heap sort’s space complexity is a constant O(1) due to its auxiliary storage.
Whether you’re a coding engineer gunning for a software developer or software engineer role, a tech lead, or targeting management positions at top companies, IK offers courses specifically designed for your needs to help you with your technical interview preparation!
If you’re looking for guidance and help with getting started, sign up for our FREE webinar. As pioneers in technical interview preparation, we have trained thousands of software engineers to crack the most challenging coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
Attend our webinar on
"How to nail your next tech interview" and learn