Heapsort Time Complexity Analysis
You'll learn: Why heapsort consistently runs in O(n log n) time regardless of input order.
The Two Phases of Heapsort
Heapsort performs two distinct operations: building the initial heap and repeatedly extracting the maximum element. Understanding each phase's cost reveals the overall complexity.
Phase 1: Building the Heap
Converting an unsorted array into a max-heap takes O(n) time. This might seem counterintuitive since we have n elements, but the "heapify-down" operations on upper levels affect fewer elements. The mathematical analysis shows most elements are near the bottom of the heap and require minimal work.
Phase 2: Extraction Loop
After building the heap, we extract the maximum element n times. Each extraction:
- Swaps the root with the last element: O(1)
- Performs heapify-down from the root: O(log n)
Since we do this n times, the extraction phase costs n × O(log n) = O(n log n).
All Cases Are O(n log n)
Best-case: Even if the array is already sorted, heapsort still builds the heap (O(n)) and performs all n extractions with heapify operations (O(n log n)). Total: O(n log n).
Average-case: Random data requires the same heap-building and extraction steps. Total: O(n log n).
Worst-case: No input arrangement can make the heap operations fundamentally worse. Each heapify-down is bounded by the tree height (log n). Total: O(n log n).
Why This Matters
Unlike quicksort, heapsort has no worst-case quadratic behavior. The logarithmic factor comes directly from the heap's tree height, which depends only on the number of elements, not their arrangement.
Key Takeaway: Heapsort guarantees O(n log n) time complexity in all cases—best, average, and worst—making it predictable but typically slower than well-implemented quicksort in practice due to cache behavior.