Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Interview Kickstart has enabled over 21000 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.

If you are preparing for a tech interview, check out our technical interview checklist, interview questions page, and salary negotiation e-book to get interview-ready!

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:

- What Is Heap Sort?
- Binary Heap
- Heapify Method
- Applications of Heap Sort
- How Does Heap Sort Work?
- Heap Sort Algorithm
- Heap Sort Pseudocode
- Heap Sort Code
- Heap Sort Complexities
- Strengths and Weaknesses of Heap Sort
- FAQs on Heap Sort

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:

- All levels except the bottom-most level are completely filled.
- All nodes in the bottom-most level are as far left as possible.
- The last level may or may not be completely filled.

**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**:

- In a
*max heap*, the*value of a node*is always >= the*value of each of its children*. - In a
*min heap*, the*value of a parent*is always <= the*value of each of its children*.

**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:

- Creates a heap from the input array.
- Then sorts the array by taking advantage of a heap's properties.

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:**

- Start at the bottom of the tree.
- Iterate through all the nodes as we travel to the top.
- At each step, ensure that the node and all its children form a valid max heap.

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:

- Go to the
**right-most node**in the**second bottom-most layer**, which has any**children**. - Process that right-most node to make sure it
**forms a MaxHeap with its children** - Traverse to the node to its
**left**and repeat the process. - At the end of the level, we jump to the right-most node of the level above it.

This journey ends when we eventually reach the topmost node and process it.

**Let’s see this in more detail:**

- Compare the
*value of the node*with the*value of the child nodes*. If the*parent's value*is more than each of the*values of the child nodes*, do nothing. - If the
*value of a child node*is more than*the parent node*,*swap the values*between the parent and the child node. (If both the child nodes have a higher value than the parent, swap the parent’s value with the value of the child who has the greater value of the two children.) - Now, for the child node that got updated, we repeat steps 1 and 2.

**Recursion:**

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.

**Bottom-to-top traversal: **

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:

- When sorting
*in-place*, we can use a max heap to sort the array in ascending order and a min heap to sort the array in descending order. - If sorting doesn’t have to be
*in-place*, we can use an auxiliary array to place the extracted element from the heap’s top in its correct position, whether we use a min heap or a max heap for the sorting.

But even when sorting is not the aim, a min/max heap in itself is a useful construction:

- The root element of a max heap always contains the maximum element.
- The root element of a min heap always has the minimum element.

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:

- Implementation of priority queues
- Security systems
- Embedded systems (for example, Linux Kernel)

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:

**Swapping**the*root element*with the*last element of the array*and decreasing the length of the heap array by one. (In heap representation, it is equivalent to swapping the root with the bottom-most and right-most leaf and then deleting the leaf.)**Restoring**heap properties (*reheapification*)*after each deletion*, where we need to apply the heapify method*only on the root node.*The subtree heaps will still have their heap properties intact at the beginning of the process.**Repeating**this process until every element in the array is sorted: Root removal, its storage i*n the position of the highest index value used by the heap*, and heap length decrement.

- On a
**max heap**, this process will sort the array in**ascending order.** - On a
**min heap**, this process will sort in**descending order**.

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:

**Creating a heap**from the currently unsorted elements of the array.**Swapping the root element with the last element**of the heap (right-most leaf node)**Reducing heap size**by 1.

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.

```
Array A, size N
heapSort()
For all non-leaf elements (i=N/2-1;i>=0;i--)
Build Heap (Heapify)
Initialize indexEnd
While indexEnd>1
Swap(A[0],A[indexEnd]
indexEnd=indexEnd-1
Build heap (apply heapify on the root node), considering array from A[0] to A[indexEnd]
Output the sorted array[]
end heapSort()
```

We have implemented the heap sort algorithm to sort in ascending order in C++:

The Heap Sort Program

```
#include
using namespace std;
void heapify(int array[], int sizeHeap, int parentIndex)
{
// Establishing a relationship between indices of a node and indices of
// its left and right children
int larger = parentIndex;
int leftChildIndex = 2 * parentIndex + 1;
int rightChildIndex = 2 * parentIndex + 2;
// Making sure the parent is greater than or equal to its left and right
// children
if (leftChildIndex < sizeHeap && array[leftChildIndex] > array[larger])
larger = leftChildIndex;
if (rightChildIndex < sizeHeap && array[rightChildIndex] > array[larger])
larger = rightChildIndex;
// Swap and heapify if parent/root is not the largest
if (larger != parentIndex)
{
swap(array[parentIndex], array[larger]);
heapify(array, sizeHeap, larger);
}
}
void heapSort(int array[], int sizeArray)
{
// Creating max heap, iterating for all non=leaf indices, since leaf
// indices don't have children to check for
for (int nonleafNodeIndex = sizeArray / 2 - 1; nonleafNodeIndex >= 0; nonleafNodeIndex--)
heapify(array, sizeArray, nonleafNodeIndex);
// Swap the root element of the heap with the last heap index, the
// Reduce heap size till it becomes 2 (last heap index
// is 1)
for (int lastHeapIndex = sizeArray - 1; lastHeapIndex >= 1; lastHeapIndex--)
{
swap(array[0], array[lastHeapIndex]);
// Heapifying root element so that the highest element is again at the
// root
heapify(array, lastHeapIndex, 0);
}
}
int main()
{
int array[] = {77, 15, 91, 21, 6, 46};
int sizeArray = sizeof(array) / sizeof(array[0]);
heapSort(array, sizeArray);
for (int i = 0; i < sizeArray; ++i)
cout << array[i] << " ";
}
```

**Output:**

```
6 15 21 46 77 91
```

The time complexity of heap sort is non-quadratic and comes out the same in the best, worst and average cases:

**O(nlogn)**

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**.

**Worst-case:**

- The worst-case run time will be experienced when the heapify method is run on
**a node smaller than all of its children**. This means the node has to be swapped through all of its levels to position it at the leaf level. So the worst-case run time will be a function of the height of the subtree, h. - Thus, the worst-case time complexity of each heapify method invocation is O(h). This height h is not a constant. At the bottom of the tree, h is 0, and at the top, h is equal to log2N.

**The time complexity for calling the heapify method for all the tree nodes** (from bottom to top):

- Taking advantage of the properties of Big-O notation, in the last step, we raised the upper limit of the summation from lg(N) to ∞. This will help us simplify the calculation. We’ll do so with the help of known mathematical properties involving the summation of numeric expressions from 0 to ∞.
- We will use the following mathematical property:

- We can notice that in our equation, we can use the above property by replacing
*x*with*1/2*. So, our equation now becomes:

- Thus, the first step of heap sort, which is building a heap out of a randomly arranged array, can be done in
**O(N)**.

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.

**Swapping:**Swapping the max element with the bottom level right-most element and reducing the heap size can be done in constant time,**O(1)**.**Reheapification**: In the worst case, the new value at the root position will have to be swapped log(N) times to be sent to the bottom of the heap to achieve a MaxHeap once again. So each reheapification after the extraction costs**O(logN)**.

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))**

=**O(Nlog(N))**

Heap sort’s space complexity is a constant **O(1)** due to its auxiliary storage.

- No quadratic worst-case run time.
- It is an in-place sorting algorithm and performs sorting in
**O(1)**space complexity. - Compared to quicksort, it has a better worst-case time complexity —
**O(nlog n)**.

The best-case complexity is the same for both quick sort and heap sort —**O(nlog n)**. - Unlike merge sort, it does not require extra space.
- The input data being completely or almost sorted doesn’t make the complexities suffer.
- The average-case complexity is the same as that of merge sort and quicksort.

- Heap sort is typically not stable since the operations on the heap can change the relative order of equal key items. It’s typically an unstable sorting algorithm.
- If the input array is huge and doesn’t fit into the memory and partitioning the array is faster than maintaining the heap, heap sort isn’t an option. In such cases, something like merge sort or bucket sort, where parts of the array can be processed separately and parallelly, works best.

**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

Hosted By

Ryan Valles

Founder, Interview Kickstart

Our tried & tested strategy for cracking interviews

The 4 areas you must prepare for

How you can accelerate your learnings

- Designed by 500 FAANG+ experts
- Live training and mock interviews
- 17000+ tech professionals trained

00

Days

:

00

Hrs

:

00

Mins

:

00

Secs