Heap Sort is a comparison-based sorting algorithm that leverages the properties of a heap, a specialized binary tree structure. It first builds a heap from the input array, then repeatedly extracts the maximum (or minimum) element and places it at its correct position in the array.

The key idea is that a heap allows efficient access to the largest or smallest element, making each extraction step fast. This leads to a consistent time complexity of O(n log n), regardless of the input.

Heap Sort is not stable, but it is in-place and does not require extra memory like Merge Sort, making it useful in memory-constrained environments.

In this chapter, you will learn how heaps work, how to build and maintain them, and how Heap Sort uses these operations to sort an array efficiently.

Heap sort is a comparison-based sorting algorithm that uses a binary heap to organize elements. The core idea is simple: if you can efficiently find and remove the maximum element, you can sort an array by repeatedly extracting the max and placing it at the end.

Before diving into the algorithm, let us make sure the underlying data structure is clear.

The Max-Heap Property

A max-heap is a complete binary tree where every parent node is greater than or equal to its children. The root of the tree always holds the largest element. This property applies recursively, so every subtree is also a valid max-heap.

Here is what a max-heap looks like:

The root (10) is larger than both children (5, 3). Node 5 is larger than both of its children (4, 1). Every parent dominates its children, which is exactly the max-heap property.

Array Representation

The beauty of a binary heap is that you do not need pointers or tree nodes. A simple array does the job. You store the tree level by level, left to right. For any element at index i:

The tree above maps to an array like this:

Index 0 holds the root (10). Its left child is at index 1 (value 5), and its right child is at index 2 (value 3). Node at index 1 has children at indices 3 and 4. No extra memory, no pointer overhead. Just a flat array with implicit tree structure.

This array-based representation is what makes heap sort an in-place algorithm. We rearrange the input array itself into a heap, then sort it, all without allocating additional storage.

The algorithm has two main phases:

Let us look at each phase in detail.

Phase 1: Build the Max-Heap

We need to rearrange the input array so it satisfies the max-heap property. The key operation here is heapify (also called sift-down), which takes a node that might violate the heap property and pushes it down to its correct position.

How heapify works:

To build the entire heap, we call heapify on every non-leaf node, starting from the bottom of the tree and working upward. Leaf nodes (the bottom half of the array) are already valid heaps by themselves, they have no children to violate anything. So we start from the last non-leaf node, which is at index (n / 2) - 1.

Why bottom-up and not top-down? If we started from the root and worked down, each heapify call might need to push elements through the entire height of the tree. By starting from the bottom, most nodes are near the leaves where the tree is short. This is why building a heap takes O(n) time instead of O(n log n). We will explain this more in the complexity section.

Phase 2: Extract Elements

Once we have a max-heap, the largest element sits at index 0 (the root). To sort the array:

Each extraction places the next-largest element at the end of the array. After all extractions, the array is sorted in ascending order.

Think of it this way: each swap "retires" the largest remaining element to the back of the array. The heap occupies the front portion, and the sorted section grows from the back. Eventually the heap shrinks to nothing and the entire array is sorted.

The heapify function is the workhorse. It compares a node with its children, swaps with the largest if needed, and recurses down the tree. The heapSort function simply orchestrates the build phase and the extraction phase.

Let us trace through heap sort with the array [4, 10, 3, 5, 1].

Phase 1: Building the Max-Heap

The array has 5 elements, so the last non-leaf node is at index 5 / 2 - 1 = 1.

Initial array: [4, 10, 3, 5, 1]

The initial tree looks like this:

Step 1: Heapify index 1 (value 10)

Node 10 has children 5 (index 3) and 1 (index 4). Since 10 > 5 and 10 > 1, no swap is needed.

Array after step 1: [4, 10, 3, 5, 1] (unchanged)

Step 2: Heapify index 0 (value 4)

Node 4 has children 10 (index 1) and 3 (index 2). The largest is 10, so we swap 4 and 10.

Array becomes: [10, 4, 3, 5, 1]

Now we recurse on index 1 (where 4 landed). Node 4 has children 5 (index 3) and 1 (index 4). The largest is 5, so we swap 4 and 5.

Array becomes: [10, 5, 3, 4, 1]

Node 4 is now at index 3, which is a leaf. Done.

The max-heap is built:

Every parent is now greater than or equal to its children. The max-heap property is satisfied.

Phase 2: Extracting Elements

Extraction 1: Swap root (10) with last element (1). Reduce heap size to 4. Heapify root.

Extraction 2: Swap root (5) with last heap element (1). Reduce heap size to 3. Heapify root.

Extraction 3: Swap root (4) with last heap element (3). Reduce heap size to 2. Heapify root.

Extraction 4: Swap root (3) with last heap element (1). Reduce heap size to 1. Done.

Final sorted array: [1, 3, 4, 5, 10]

The pipe character | in the traces above separates the active heap (left) from the sorted portion (right). With each extraction, the heap shrinks and the sorted section grows until the entire array is in order.

Why Building a Heap Takes O(n)

This is one of the most commonly asked interview questions about heap sort, and the answer is counterintuitive. You might think: we call heapify n/2 times, and each call takes O(log n), so the total should be O(n log n). But that overestimates the work.

The key insight is that most nodes are near the bottom of the tree, where heapify does very little work. In a complete binary tree with n nodes:

The total work is:

This series converges to a constant (approximately 2), so the total work is O(n).

Why the Extraction Phase Takes O(n log n)

During the extraction phase, we perform n - 1 extractions. Each extraction involves a swap (O(1)) and a heapify from the root (O(log n)). Unlike the build phase, every heapify during extraction starts from the root and might travel all the way down to the leaves. So the total is O(n log n), and there is no shortcut here.

Good for

Not ideal for

Comparison with Other O(n log n) Sorts

Heap sort occupies a unique niche: it is the only comparison-based sort that offers both O(n log n) worst-case time and O(1) extra space. When both of those constraints matter simultaneously, heap sort is your best option.