Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to efficiently find and extract the maximum (or minimum) element. It was first proposed by J. W. J. Williams in 1964 and later improved by Robert W. Floyd. The algorithm works by building a max heap from the input array, then repeatedly extracting the maximum element and placing it at the end of the sorted portion. Heap Sort guarantees O(n log n) time in all cases and requires only O(1) extra space.

Historical Context

Williams introduced Heap Sort along with the binary heap data structure itself in a 1964 paper published in Communications of the ACM. Floyd soon after published an improvement to the heap construction phase, showing that building a heap could be done in O(n) time rather than O(n log n) using a bottom-up approach. The binary heap went on to become one of the most important data structures in computer science, forming the basis of priority queues used in Dijkstra's shortest path algorithm, Huffman coding, and event-driven simulations.

How It Works

1. Build max heap: Rearrange the array so it satisfies the max-heap property -- every parent node is greater than or equal to its children. A binary heap is stored as an array where the children of node at index i are at indices 2i+1 and 2i+2. Floyd's bottom-up construction starts from the last non-leaf node and applies the sift-down (heapify) operation to each node, working upward. This builds the heap in O(n) time.
2. Extract maximum: Swap the root (the maximum element) with the last element in the heap, then reduce the heap size by one. The maximum element is now in its final sorted position.
3. Restore heap: The root may now violate the max-heap property. Apply sift-down on the root: compare it with its children and swap with the larger child, repeating down the tree until the heap property is restored. This takes O(log n) time.
4. Repeat: Continue extracting the maximum and restoring the heap until the heap is empty. The array is now sorted in ascending order.

The sift-down operation is the key primitive. Starting at a node, it compares the node with both children and swaps with the larger child if necessary, continuing down the tree until the node is larger than both children or reaches a leaf.

Complexity

The build-heap phase takes O(n), and the extraction phase performs n sift-down operations each taking O(log n), giving O(n log n) total. Unlike Quick Sort, there is no pathological input that causes degradation.

Comparison with Other Algorithms

Compared to Merge Sort, Heap Sort has the advantage of sorting in-place with O(1) extra space, while Merge Sort requires O(n) auxiliary memory. However, Merge Sort is stable and typically faster in practice due to its sequential memory access pattern. Compared to Quick Sort, Heap Sort has a better worst-case guarantee (O(n log n) vs O(n^2)), but Quick Sort is usually faster on average because its memory access pattern has better cache locality. Heap Sort accesses elements at widely separated indices during sift-down, causing frequent cache misses on modern hardware. This cache-unfriendly behavior is Heap Sort's main practical disadvantage.

Role in Introsort

Heap Sort plays a critical role in Introsort (introspective sort), the hybrid sorting algorithm used in many standard library implementations including C++'s std::sort. Introsort begins with Quick Sort for its excellent average-case performance, but monitors the recursion depth. If the recursion depth exceeds 2 * log(n), indicating that Quick Sort is approaching its O(n^2) worst case, Introsort switches to Heap Sort as a fallback to guarantee O(n log n) overall performance. This combination gives the best of both worlds: Quick Sort's speed in the common case and Heap Sort's worst-case guarantee.

When to Use

Heap Sort is the right choice when guaranteed O(n log n) performance and minimal memory usage are both required. It is useful in embedded systems and real-time applications where memory allocation is restricted and worst-case bounds must be predictable. It is not stable, so it should not be used when the relative order of equal elements must be preserved.