Heap Sort

Heap Sort is a cornerstone comparison-based sorting algorithm that combines the efficiency of guaranteed $O(n\log n)$ performance with the practical advantage of in-place sorting, meaning it requires only a constant, $O(1)$, amount of extra memory. Unlike Quicksort, which can degrade to $O(n^2)$ time in worst-case scenarios, Heap Sort provides a reliable worst-case bound, making it a valuable tool for sorting arrays where predictable performance is critical, such as in real-time systems or memory-constrained environments. Its operation is an elegant application of the heap data structure to transform the unsorted array itself into a sorted one.

Understanding the Heap Data Structure

Before diving into the algorithm, you must grasp the underlying data structure. A binary heap is a complete binary tree that satisfies the heap property. In a max-heap, which Heap Sort uses, the property states that for any given node, its value is greater than or equal to the values of its children. Consequently, the largest element in the entire heap is always stored at the root node.

The genius of the heap for sorting is its efficient representation. A complete binary tree can be perfectly mapped onto an array. For a node at index $i$ (using zero-based indexing), we can find its family using simple arithmetic:

• Parent index: $\lfloor (i-1)/2\rfloor$
• Left child index: $2i+1$
• Right child index: $2i+2$

This array representation eliminates the need for pointer-based nodes, allowing the entire sorting process to happen within the original array bounds. The core subroutine that maintains the heap property is the heapify (or siftDown) operation.

The Heapify Process

The heapify function ensures that the subtree rooted at a given index $i$ obeys the max-heap property. It assumes that the subtrees of node $i$ are already valid heaps. The operation works by comparing the node with its left and right children. If the node is smaller than the largest child, it swaps places with that child. This swap may violate the heap property in the new subtree, so heapify recursively calls itself on the affected child index.

Consider a small example within an array: [1, 12, 9]. The root (index 0, value 1) violates the max-heap property because its left child (index 1, value 12) is larger.

1. Identify largest child: 12.
2. Swap root (1) with left child (12). Array is now [12, 1, 9].
3. Recursively call heapify on index 1 (now holding value 1). It compares with its child (9) and swaps, resulting in [12, 9, 1].

The time complexity of heapify on a subtree of height $h$ is $O(h)$, which translates to $O(\log n)$ for a tree with $n$ elements.

Phase 1: Building the Max-Heap

The first major phase of Heap Sort is to transform the entire unsorted input array into a valid max-heap. A key insight is that you can build this heap from the bottom up. You start by calling heapify on the last non-leaf node in the tree and work backwards to the root.

Why start from the last non-leaf node? Its index is $\lfloor n/2\rfloor -1$. Leaf nodes (elements with no children) are, by definition, trivial single-element heaps that already satisfy the heap property. By processing nodes in reverse order, you ensure that when you call heapify on a given node, its child subtrees are already valid heaps—which is the precondition heapify requires.

Building the heap has a time complexity of $O(n)$, which is more efficient than the naive approach of inserting $n$ elements one-by-one, which would be $O(n\log n)$. This linear-time build is crucial for Heap Sort's overall efficiency.

Phase 2: Extracting Elements to Sort

Once the array is a max-heap, the root contains the largest element. The sorting phase begins:

1. Swap the root (largest element, at index 0) with the last element in the current heap (at index end).
2. Decrease the heap size by one, effectively removing the now-sorted largest element from the heap structure and placing it in its final sorted position at the end of the array.
3. Restore the heap property for the new root, which is likely a small value, by calling heapify on index 0. This heapify call only operates on the reduced heap of size end.

You repeat this extract-max/restore-heap process until the heap size is reduced to one. Each extraction and subsequent heapify costs $O(\log n)$, and you perform this $n-1$ times, resulting in $O(n\log n)$ time for this phase. The sorted array accumulates from the end to the beginning in ascending order. Because the largest remaining element is always moved to the end of the active heap region, the algorithm is in-place.

Common Pitfalls

Off-by-One Errors in Heapify Child Indexing: When implementing the child index calculations 2*i + 1 and 2*i + 2, a common mistake is to use one-based indexing formulas on a zero-based array, or to forget to check if a child index is still within the bounds of the current heap size before comparing values. Always verify that the child index is < heapSize.

Misunderstanding Heap Sort's Stability: Heap Sort is not a stable sort. Stability means that elements with equal values retain their relative order from the original input. During the heapify and swap operations, elements that are equal can be moved past each other in non-deterministic ways. For example, sorting [(5, a), (5, b)] by the first key may result in [(5, b), (5, a)]. If you require a stable sort, algorithms like Merge Sort are necessary.

Confusing Time Complexity of the Build-Heap Phase: It's easy to assume that building the heap must take $O(n\log n)$ time because you perform $O(n)$ calls to heapify. However, a more precise analysis shows that most heapify calls operate on very small subtrees near the bottom. The sum of the heights of all nodes leads to the linear $O(n)$ bound. Treating the build phase as $O(n\log n)$ underestimates the algorithm's efficiency.

Summary

• Heap Sort is an efficient, in-place sorting algorithm with a guaranteed $O(n\log n)$ worst-case and average-case time complexity, requiring only $O(1)$ auxiliary space.
• It operates in two key phases: first, building a max-heap from the unsorted array in $O(n)$ time, and second, repeatedly extracting the maximum element and restoring the heap property to produce the sorted sequence.
• The algorithm is built upon the heapify subroutine, which maintains the heap property in $O(\log n)$ time and is used extensively in both phases.
• A significant advantage is its reliable $O(n\log n)$ performance, avoiding the worst-case degradation that can affect Quicksort, though it is generally slower in practice due to more frequent element comparisons and swaps.
• Its main limitations are that it is not stable and typically exhibits poorer cache performance compared to algorithms like Quicksort or Merge Sort due to its non-sequential data access patterns.