Heap Sort
Heap sort leverages the heap data structure, specifically a max-heap, to sort an array in place. A max-heap is a complete binary tree where every parent no...
Building a Max-Heap
Heap sort leverages the heap data structure, specifically a max-heap, to sort an array in place. A max-heap is a complete binary tree where every parent node is greater than or equal to both its children. In array representation, the parent of the node at index i is at index (i minus 1) divided by 2, the left child is at 2i plus 1, and the right child is at 2i plus 2.
The heapify operation is the fundamental building block. It takes a subtree rooted at index i and restores the max-heap property by sifting the element at i downward until it is in the correct position. Pseudocode: find the largest of the node at i, its left child, and its right child. If the largest is not i, swap the element at i with the largest child and recursively heapify the subtree rooted at the largest child index.
Building a max-heap from an unsorted array uses the build-heap algorithm. Call heapify on every non-leaf node, starting from the last non-leaf at index floor of (n/2) minus 1 down to index 0. This produces a valid max-heap in O(n) time, which is more efficient than inserting elements one by one into an empty heap, which would take O(n log n).
A worked example: convert the array 4, 10, 3, 5, 1 into a max-heap. n is 5, so start heapify at index 1. At index 1 (value 10), children are at indices 3 (value 5) and 4 (value 1). 10 is already the largest, no swap. At index 0 (value 4), children are at indices 1 (value 10) and 2 (value 3). 10 is the largest, swap 4 and 10: heap is now 10, 4, 3, 5, 1. Heapify index 1: value 4, children are 5 and 1. Swap 4 and 5: heap is now 10, 5, 3, 4, 1.
Time complexity for build-heap is O(n). Time complexity for a single heapify call is O(log n). Space complexity for build-heap is O(1) extra space since it operates in place.
Interview tip: the O(n) build-heap complexity surprises many candidates who expect O(n log n). The proof relies on the fact that most nodes are near the bottom of the heap and have short sift-down distances, so the total work sums to a geometric series converging to O(n).
Sorting with the Heap
Once the array is a valid max-heap, the sorting phase is straightforward. The maximum element is always at the root, which is index 0 in the array representation. To sort in ascending order, repeatedly extract the maximum by swapping the root with the last element of the heap, shrink the heap size by one, and restore the heap property by calling heapify on the new root.
Pseudocode for heap sort: first call build-heap to convert the array into a max-heap. Then for i from n-1 down to 1, swap array at 0 with array at i, call heapify on the heap of size i with root at index 0.
A worked example continuing from the previous section: starting with the max-heap 10, 5, 3, 4, 1. Swap index 0 and index 4: array becomes 1, 5, 3, 4, 10. Heap size is now 4. Heapify index 0 with size 4: 1 is compared with children 5 and 3. Swap 1 and 5: 5, 1, 3, 4, 10. Heapify index 1 with size 4: 1 is compared with children 4 (index 3). Swap 1 and 4: 5, 4, 3, 1, 10. Swap index 0 and index 3: 1, 4, 3, 5, 10. Continue until sorted: 1, 3, 4, 5, 10.
Time complexity for heap sort is O(n log n) in all cases: best, average, and worst. The build-heap phase takes O(n) and the extraction phase makes n minus 1 calls to heapify, each costing O(log n). Space complexity is O(1) because everything is done in place with no auxiliary arrays.
Heap sort is not stable. The swap operation can move an element past another element with the same key, disrupting relative order.
Interview tip: emphasize that heap sort is the only commonly taught comparison-based sorting algorithm that is both O(n log n) worst case and O(1) space. Merge sort achieves O(n log n) worst case but requires O(n) extra space. Quick sort is O(1) space but O(n squared) worst case without careful pivot selection.
Heap Sort vs Quick Sort and Merge Sort
Heap sort occupies an interesting position in the sorting algorithm landscape because it has guaranteed O(n log n) performance and O(1) extra space, two properties that no other commonly used comparison sort achieves simultaneously. However, in practice heap sort runs slower than both quick sort and merge sort on most real workloads, and understanding why is important.
The primary reason for heap sort's slower practical performance is cache behavior. Quick sort and merge sort process elements in contiguous memory regions, which load efficiently into CPU cache lines. Heap sort accesses elements by jumping to parents and children at indices like i, 2i, and i/2 in the array. These jumps create cache misses because the accessed elements are far apart in memory, especially for large heaps. For a heap of 1 million elements, accessing the children of a node near the root requires jumping roughly 500,000 positions forward in the array.
A second reason is that heap sort does not benefit from nearly sorted input. Build-heap always takes O(n) time regardless of initial order, and the sorting phase always makes n minus 1 heapify calls. Merge sort with run detection (Timsort) and quick sort with early termination can approach O(n) on nearly sorted input.
Despite this, heap sort's worst-case guarantee makes it valuable as a fallback within introsort, where it prevents quick sort's O(n squared) worst case. Heap sort is also useful when you only need the top k elements of a large dataset. Building a min-heap of size k and processing the remaining n minus k elements takes O(n log k) time, which is optimal for this problem.
A worked example: finding the 10 largest elements in a stream of 1 million integers. Maintain a min-heap of size 10. For each new element, if it is larger than the heap's minimum, remove the minimum and insert the new element. After all million elements, the heap contains the 10 largest. Total time: O(n log k) where k is 10, which is essentially O(n).
Interview tip: when asked to compare heap sort with quick sort and merge sort, say that heap sort is theoretically ideal but cache-unfriendly in practice, making introsort (which uses heap sort only as a worst-case backstop) the best of all worlds.