Heap Sort

Introduction

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It was proposed by J. W. J. Williams in 1964 and later improved by Robert W. Floyd. The algorithm combines the speed of merge sort's O(n log n) guarantee with the space efficiency of selection sort's in-place operation.

The algorithm works in two phases. First, it builds a max-heap from the input array, which rearranges the elements so that the largest element is at the root. Then, it repeatedly extracts the maximum element from the heap and places it at the end of the array, reducing the heap size by one each time. After all elements have been extracted, the array is sorted in ascending order.

Heap sort guarantees O(n log n) time complexity in all cases -- best, average, and worst -- and requires only O(1) additional space. These properties make it an excellent choice when worst-case performance guarantees and minimal memory usage are both required, although its poor cache locality means it is typically slower than quicksort in practice.

"Heap sort is an elegant algorithm which uses the heap data structure. Its worst-case running time has a better leading constant than that of merge sort, and it sorts in place." -- Thomas H. Cormen, Introduction to Algorithms

How It Works

Binary Heap Prerequisite

A binary heap is a complete binary tree that satisfies the heap property. In a max-heap, every parent node is greater than or equal to its children. A binary heap can be efficiently represented as an array where, for an element at index i:

• Its left child is at index 2i + 1
• Its right child is at index 2i + 2
• Its parent is at index (i - 1) / 2 (integer division)

Algorithm Steps

1. Build a max-heap from the unsorted array. This is done by calling the "heapify" (also called "sift down") operation on each non-leaf node, starting from the last non-leaf node and working toward the root.
2. Extract the maximum: The root of the max-heap (the largest element) is swapped with the last element of the heap.
3. Reduce heap size: Decrease the heap size by one, effectively placing the extracted maximum in its final sorted position.
4. Restore the heap property: Call heapify on the root to restore the max-heap property in the reduced heap.
5. Repeat steps 2-4 until the heap size is 1.

The Heapify Operation

Heapify (sift down) corrects a single violation of the heap property. Given a node whose children are roots of valid max-heaps, heapify moves the node down the tree by swapping it with its largest child until the heap property is restored. This operation takes O(log n) time because the height of a complete binary tree with n nodes is log n.

Algorithm and Pseudocode

Heap Sort

procedure heapSort(A : array) n := length(A) // Phase 1: Build max-heap // Start from the last non-leaf node and heapify each for i := n/2 - 1 down to 0 do heapify(A, n, i) end for // Phase 2: Extract elements one by one for i := n - 1 down to 1 do swap(A[0], A[i]) // Move current max to end heapify(A, i, 0) // Restore heap on reduced array end forend procedure

Heapify (Sift Down)

procedure heapify(A : array, heapSize : int, root : int) largest := root left := 2 * root + 1 right := 2 * root + 2 // Check if left child is larger than root if left < heapSize and A[left] > A[largest] then largest := left end if // Check if right child is larger than current largest if right < heapSize and A[right] > A[largest] then largest := right end if // If largest is not the root, swap and continue heapifying if largest != root then swap(A[root], A[largest]) heapify(A, heapSize, largest) // Recursively heapify the affected subtree end ifend procedure

The heapify procedure compares a node with its two children and swaps it with the larger child if necessary, then recurses on the affected subtree. The recursion terminates when the node is larger than both children or when it reaches a leaf.

Time and Space Complexity

Detailed Analysis

Build-heap phase: Although each heapify call is O(log n) and there are O(n) calls, the total cost of building the heap is actually O(n), not O(n log n). This is because most nodes are near the leaves and require very little sifting. More precisely, nodes at height h require O(h) work, and there are at most n / 2^(h+1) nodes at height h. The sum over all heights gives O(n).

Extraction phase: There are n - 1 extraction steps, each requiring a heapify operation of O(log n) cost. This phase dominates, giving O(n log n) total.

Space Complexity: O(1). Heap sort is an in-place algorithm. The heap is built within the original array, and only a constant number of additional variables are needed. If heapify is implemented recursively, it uses O(log n) stack space, but an iterative implementation requires only O(1).

Stability: Heap sort is not stable. The swap operations during heap construction and extraction can change the relative order of elements with equal keys.

Worked Example

Sort the array [4, 10, 3, 5, 1] using heap sort.

Phase 1: Build Max-Heap

Array indices: [0:4, 1:10, 2:3, 3:5, 4:1]. Last non-leaf node is at index 1 (parent of index 3 and 4).

Max-heap built: [10, 5, 3, 4, 1]. The root (10) is the maximum element.

Phase 2: Extract and Sort

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

Advantages and Disadvantages

Advantages

• Guaranteed O(n log n): No worst-case degradation. Unlike quicksort, heap sort never exhibits quadratic behavior.
• In-place: Requires only O(1) additional memory when heapify is implemented iteratively.
• No pathological inputs: Performance is consistent regardless of input distribution.
• Useful as a fallback: Used in introsort as the backup algorithm when quicksort's recursion depth becomes excessive.
• Deterministic: Does not rely on random number generation, making it suitable for security-sensitive applications.

Disadvantages

• Poor cache performance: The parent-child relationships in the heap cause non-sequential memory access, leading to many cache misses. This makes heap sort 2-5 times slower than quicksort in practice.
• Not stable: Cannot preserve the relative order of equal elements.
• Not adaptive: Does not take advantage of existing order in the input data.
• Higher constant factors: The overhead of heap operations makes it slower than merge sort for most practical inputs.

Comparison with Other Algorithms

Heap Sort vs. Quick Sort: Quicksort is faster in practice (2-3x) due to superior cache locality, but heap sort guarantees O(n log n) worst-case time. Introsort resolves this trade-off by using quicksort as the primary algorithm and switching to heap sort when the recursion depth suggests worst-case behavior.

Heap Sort vs. Merge Sort: Both guarantee O(n log n) time. Merge sort is stable and often faster due to sequential memory access during merging. Heap sort uses O(1) space versus merge sort's O(n). Choose heap sort when memory is constrained; choose merge sort when stability is required.

Heap Sort vs. Selection Sort: Heap sort can be viewed as an optimized selection sort. Both repeatedly select the extreme element, but heap sort uses a heap to find it in O(log n) time instead of O(n), improving the overall complexity from O(n^2) to O(n log n).

Implementation Notes

Iterative Heapify

The recursive heapify can be converted to an iterative version to avoid O(log n) stack space:

procedure heapifyIterative(A : array, heapSize : int, root : int) while true do largest := root left := 2 * root + 1 right := 2 * root + 2 if left < heapSize and A[left] > A[largest] then largest := left end if if right < heapSize and A[right] > A[largest] then largest := right end if if largest == root then break swap(A[root], A[largest]) root := largest end whileend procedure

Bottom-Up Heap Sort

A variant that reduces the number of comparisons by approximately 50%. Instead of sifting down from the root by comparing with both children at each level, it first finds the path of maximum children to a leaf, then sifts up from the leaf to find the correct position. This exploits the fact that extracted elements usually belong near the bottom of the heap.

Building the Heap in O(n)

The build-heap operation runs in O(n), not O(n log n), despite making O(n) heapify calls. The key insight is that most nodes are near the bottom of the tree and require very little work. The exact number of operations is bounded by the sum: n * sum(h / 2^h) for h = 0 to log n, which converges to 2n.

Min-Heap Variant

Using a min-heap instead of a max-heap sorts the array in descending order. To sort in ascending order with a min-heap, you would need an auxiliary array, which defeats the purpose of in-place sorting. Therefore, the max-heap variant is standard for ascending-order heap sort.

Applications

• Introsort fallback: The C++ STL std::sort uses introsort, which begins with quicksort and falls back to heap sort when the recursion depth exceeds 2 * log(n), preventing worst-case quadratic behavior.
• Embedded and real-time systems: Heap sort's O(1) space and guaranteed O(n log n) time make it suitable for systems with strict memory and timing constraints.
• Priority queue operations: The heap data structure underlying heap sort is the foundation of priority queues, which are used in Dijkstra's algorithm, Huffman coding, event-driven simulations, and operating system schedulers.
• Partial sorting: Finding the k largest or smallest elements can be done efficiently with a heap in O(n + k log n) time.
• Security-critical sorting: Heap sort's deterministic O(n log n) behavior avoids algorithmic complexity attacks that can exploit quicksort's O(n^2) worst case.

References

• Williams, J. W. J. "Algorithm 232: Heapsort." Communications of the ACM, 7(6):347-349, 1964.
• Floyd, R. W. "Algorithm 245: Treesort 3." Communications of the ACM, 7(12):701, 1964.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, 4th Edition. MIT Press, 2022. Chapter 6: Heapsort.
• Sedgewick, R. and Wayne, K. Algorithms, 4th Edition. Addison-Wesley, 2011. Section 2.4: Priority Queues.
• Wegener, I. "Bottom-Up-Heapsort, a new variant of Heapsort beating, on average, Quicksort." Theoretical Computer Science, 118(1):81-98, 1993.