Heap Sort is a comparison-based sorting algorithm that uses 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.

A heap allows efficient access to the largest or smallest element, so each extraction step runs in O(log n). This produces 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, which makes it useful in memory-constrained environments.

This chapter covers how heaps work, how to build and maintain them, and how Heap Sort uses these operations to sort an array.

The core idea: if the maximum element can be found and removed efficiently, the array can be sorted by repeatedly extracting the max and placing it at the end. This depends on the underlying data structure, the heap.

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

A binary heap does not need pointers or tree nodes. A simple array stores 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). The node at index 1 has children at indices 3 and 4. The flat array encodes the tree structure implicitly, with no extra memory or pointer overhead.

This array-based representation is what makes heap sort an in-place algorithm. The input array itself is rearranged into a heap and then sorted, all without allocating additional storage.

The algorithm has two main phases:

Each phase in detail:

Phase 1: Build the Max-Heap

The input array must be rearranged to satisfy the max-heap property. The key operation 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:

Building the entire heap calls 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 because they have no children that could violate the heap property. The build phase starts from the last non-leaf node, which is at index (n / 2) - 1.

Why bottom-up and not top-down? Starting from the root and working down would require each heapify call to push elements through the entire height of the tree. Starting from the bottom means most nodes are near the leaves where the tree is short, which is why building a heap takes O(n) time instead of O(n log n). The Complexity Analysis section derives this in detail.

Phase 2: Extract Elements

Once the max-heap is built, 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.

Each swap moves 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 does the core comparison-and-swap work: it compares a node with its children, swaps with the largest if needed, and recurses down the tree. The heapSort function orchestrates the build phase and the extraction phase.

Trace heap sort on 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 swap 4 and 10.

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

Recurse on index 1 (where 4 landed). Node 4 has children 5 (index 3) and 1 (index 4). The largest is 5, so 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)

A naive analysis counts n/2 heapify calls, each O(log n), giving O(n log n). That bound is loose because it ignores where the calls happen in the tree.

Most nodes are near the bottom of the tree, where heapify does 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)

The extraction phase performs 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 can travel all the way down to the leaves. The total is O(n log n).

Stability

Heap sort is not stable. Both phases swap elements across long distances. During the build phase, sift-down moves a node down through several levels, jumping past unrelated elements. During the extraction phase, the root swaps with the last heap element before re-heapifying, which can leap one equal element over another.

For example, with the input [2, 5a, 5b, 1], after building the max-heap the structure becomes something like [5a, 2, 5b, 1] or [5b, 5a, 2, 1] depending on the heapify path. Subsequent extractions place the values back into the array in the order they exit the heap, which is not guaranteed to match the original 5a, 5b order.

A stable variant is possible by tagging each element with its original index and using that as a tiebreaker in the heap comparison, but this adds O(n) auxiliary space and forfeits heap sort's main advantage over merge sort.

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