Loading learning content...
Heap sort is beautifully simple at its core: convert an array into a heap, then repeatedly extract the maximum. Yet within this simplicity hides one of the most elegant analyses in algorithm design—the proof that building a heap takes O(n) time, not O(n log n) as a naive analysis might suggest.
In this page, we'll master both phases of heap sort. You'll understand exactly how to transform an arbitrary array into a valid max-heap efficiently, and how the extraction phase systematically produces a sorted array. More importantly, you'll understand why these operations work and why their complexity bounds are what they are.
By the end of this page, you will be able to implement the build-heap algorithm, prove its O(n) complexity, understand the extraction phase in detail, and write complete, correct heap sort code. You'll also understand the subtle mathematical reasoning behind the linear-time heap construction.
Before appreciating the optimal build-heap algorithm, let's consider the straightforward approach: insert elements one by one into an initially empty heap.
Naive Build Heap via Insertions:
For each element in arr[0..n-1]:
Insert element into heap (bubble up)
Each insertion takes O(log k) for a heap of size k. Summing over all insertions:
$$T(n) = \sum_{k=1}^{n} \log k = \log(n!) \approx n \log n - n = O(n \log n)$$
This works, but it's not optimal. The key insight is that we're doing unnecessary work. When we insert elements, we bubble them up from the bottom. But most elements are near the bottom anyway, and bubbling up from the bottom is the expensive case.
What if we could restructure our approach to do the expensive work where there are few elements, and the cheap work where there are many?
The breakthrough is reversing the direction of work. Instead of bubbling up (where the many bottom elements do the most work), we heapify down (where the many bottom elements do almost no work). This redistribution of effort transforms O(n log n) into O(n).
The efficient build-heap algorithm uses a simple but powerful idea: treat the array as an almost-complete binary tree and fix heap violations from the bottom up.
The Algorithm:
Why Bottom-Up?
Heapify requires that both children are valid heaps. By working bottom-up:
Where Is the Last Non-Leaf Node?
For an array of size n (0-indexed):
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
def heapify(arr: list, n: int, i: int) -> None: """ Restore max-heap property for subtree rooted at index i. Assumes children subtrees are already valid max-heaps. Time: O(log n) - descends at most height of tree Space: O(1) - iterative implementation """ while True: largest = i left = 2 * i + 1 right = 2 * i + 2 # Find largest among root and its children if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right # If root is largest, heap property is satisfied if largest == i: break # Swap and continue heapifying down arr[i], arr[largest] = arr[largest], arr[i] i = largest def build_max_heap(arr: list) -> None: """ Transform an arbitrary array into a valid max-heap in-place. Algorithm: 1. Start from the last non-leaf node (parent of last element) 2. Heapify each node, moving upward to the root 3. After processing root, entire array is a valid max-heap Time Complexity: O(n) - NOT O(n log n)! - Proof in the analysis section - Key: most nodes are near leaves and heapify in O(1) Space Complexity: O(1) - in-place transformation Args: arr: The array to transform into a max-heap Postcondition: For all i in [0, n//2-1]: arr[i] >= arr[2i+1] and arr[i] >= arr[2i+2] """ n = len(arr) # Last non-leaf node is at index (n // 2) - 1 # All nodes at indices n//2 to n-1 are leaves last_non_leaf = (n // 2) - 1 # Heapify all non-leaf nodes, from bottom to top # This ensures when we heapify node i, its children are already heaps for i in range(last_non_leaf, -1, -1): heapify(arr, n, i) def build_max_heap_with_trace(arr: list) -> list: """ Build max-heap with step-by-step trace for educational purposes. Returns a list of (step, index, array_state) tuples. """ trace = [] n = len(arr) trace.append(("Initial", -1, arr.copy())) last_non_leaf = (n // 2) - 1 for i in range(last_non_leaf, -1, -1): heapify(arr, n, i) trace.append((f"Heapify index {i}", i, arr.copy())) trace.append(("Complete", -1, arr.copy())) return trace # Example usageif __name__ == "__main__": # Demonstrate build-heap test_array = [4, 10, 3, 5, 1, 8, 7] print(f"Original array: {test_array}") trace = build_max_heap_with_trace(test_array.copy()) print("\nBuild-heap trace:") for step, idx, state in trace: print(f" {step}: {state}") # Verify heap property final = trace[-1][2] n = len(final) is_valid = all( final[i] >= final[2*i+1] and (2*i+2 >= n or final[i] >= final[2*i+2]) for i in range(n // 2) ) print(f"\nHeap property satisfied: {is_valid}")The claim that build-heap runs in O(n) time is surprising. After all, we call heapify (which is O(log n)) for O(n) nodes. Shouldn't the total be O(n log n)? The answer lies in the precise distribution of work.
The Key Observation:
Not all nodes heapify for log n steps. Nodes near the bottom of the tree have very short paths to travel down. Specifically:
The expensive operations happen at the top where there are few nodes. The cheap operations happen at the bottom where there are many nodes.
The Formal Analysis:
Let h = ⌊log₂ n⌋ be the height of the heap. At height k (counting from leaves as height 0):
Total work: $$T(n) = \sum_{k=0}^{h} \frac{n}{2^{k+1}} \cdot O(k) = O\left(n \sum_{k=0}^{h} \frac{k}{2^{k+1}}\right)$$
The sum $\sum_{k=0}^{\infty} \frac{k}{2^k}$ converges to 2 (this can be shown by differentiating the geometric series).
Therefore: T(n) = O(n × 2) = O(n)
| Height | Nodes at Height | Work per Node | Total Work at Level |
|---|---|---|---|
| 0 (leaves) | 16 | 0 | 0 |
| 1 | 8 | 1 | 8 |
| 2 | 4 | 2 | 8 |
| 3 | 2 | 3 | 6 |
| 4 (root) | 1 | 4 | 4 |
| Total | 31 | 26 |
Intuitive Understanding:
Think about it this way: the single root might do log n work, but it's just one node. The n/2 leaves do 0 work each. The "center of mass" of the work is near the bottom, where nodes are plentiful but work is cheap. Mathematically, the heavy tail of small work contributions outweighs the light tail of expensive work.
Comparison with Top-Down Building:
If we built the heap top-down (inserting and bubbling up), the analysis reverses:
This is why direction matters. Bottom-up heapify is fundamentally more efficient for building.
The sum Σ k/2^k = 2 is a classic result from calculus. It arises from differentiating the geometric series Σ x^k = 1/(1-x). This mathematical identity is why build-heap achieves O(n) time. The structure of binary trees and this convergent series align perfectly.
Once we have a valid max-heap, the extraction phase transforms it into a sorted array through repeated maximum extraction. This phase is conceptually simple but requires careful implementation.
The Algorithm:
Invariant:
After k extractions:
Time Analysis:
Each extraction:
Total over all extractions: $$T(n) = \sum_{k=n}^{1} O(\log k) = O(n \log n)$$
Unlike build-heap, we cannot avoid the O(n log n) bound here. Each heapify starts from the root, always traversing the maximum possible distance.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116
def extract_max(arr: list, heap_size: int) -> tuple[int, int]: """ Extract the maximum element from the heap. The maximum is moved to position (heap_size - 1), and the heap is restored for the remaining elements. Returns: Tuple of (extracted_max, new_heap_size) Time: O(log heap_size) for heapify Space: O(1) """ if heap_size <= 0: raise ValueError("Cannot extract from empty heap") if heap_size == 1: return arr[0], 0 # The maximum is at the root max_element = arr[0] # Move the last element to the root arr[0] = arr[heap_size - 1] # Put the max in its final sorted position arr[heap_size - 1] = max_element # Reduce heap size (conceptually remove the extracted maximum) new_heap_size = heap_size - 1 # Restore heap property from the root heapify(arr, new_heap_size, 0) return max_element, new_heap_size def extraction_phase(arr: list) -> None: """ Convert a max-heap into a sorted array (ascending order). Precondition: arr is a valid max-heap Postcondition: arr is sorted in ascending order Time: O(n log n) Space: O(1) """ n = len(arr) heap_size = n # Extract n-1 times (the last element is trivially in place) for i in range(n - 1, 0, -1): # Swap root (max) with last heap element arr[0], arr[i] = arr[i], arr[0] # The heap is now indices [0, i-1] # Heapify from root with reduced size heapify(arr, i, 0) def extraction_phase_with_trace(arr: list) -> list: """ Extraction phase with detailed trace for visualization. """ trace = [] n = len(arr) trace.append({ "step": "Start extraction", "heap": arr.copy(), "heap_size": n, "sorted_portion": [] }) for i in range(n - 1, 0, -1): # Before swap max_val = arr[0] # Swap and heapify arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) trace.append({ "step": f"Extract {max_val}", "heap": arr[:i], "heap_size": i, "sorted_portion": arr[i:] }) trace.append({ "step": "Complete", "heap": [], "heap_size": 0, "sorted_portion": arr.copy() }) return trace def heapify(arr: list, n: int, i: int) -> None: """Standard heapify (included for completeness).""" while True: largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest == i: break arr[i], arr[largest] = arr[largest], arr[i] i = largestWhen the heap size is 1, only one element remains. It's already in its correct position (the smallest element). We don't need to extract it—there's nothing to swap it with. This is why the loop goes from n-1 down to 1, performing exactly n-1 swaps.
Now let's put it all together into a complete, production-ready heap sort implementation. We'll combine the build-heap and extraction phases into a single cohesive function.
The Complete Algorithm:
Total Complexity:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
def heap_sort(arr: list) -> None: """ Sort an array in ascending order using heap sort. Algorithm: Phase 1 (Build Heap): Transform array into max-heap - Process nodes from bottom-up - Each node is heapified assuming children are valid heaps - Time: O(n) Phase 2 (Extract): Repeatedly extract maximum - Swap root with last heap element - Reduce heap size, heapify from root - Time: O(n log n) Time Complexity: O(n log n) in ALL cases (best, average, worst) Space Complexity: O(1) - strictly in-place Stable: No (equal elements may be reordered) Args: arr: The array to sort (modified in-place) Returns: None (arr is sorted in-place) """ n = len(arr) if n <= 1: return # Already sorted # ======================================== # Phase 1: Build Max-Heap — O(n) # ======================================== # Start from the last non-leaf node and heapify upward # Leaves don't need heapification (trivially valid heaps) for i in range((n // 2) - 1, -1, -1): _heapify(arr, n, i) # Invariant: arr[0..n-1] is now a valid max-heap # arr[0] is the maximum element # ======================================== # Phase 2: Extract Maximum — O(n log n) # ======================================== # Each iteration: # - Swaps max (at root) with last heap element # - Reduces heap size by 1 # - Heapifies to restore heap property for i in range(n - 1, 0, -1): # Swap maximum element with last element in current heap arr[0], arr[i] = arr[i], arr[0] # Restore heap property for reduced heap [0, i-1] _heapify(arr, i, 0) # Invariant: arr is sorted in ascending order def _heapify(arr: list, heap_size: int, root_index: int) -> None: """ Restore max-heap property for subtree rooted at root_index. This is an internal helper function using an iterative approach for efficiency (no stack overhead from recursion). Args: arr: The array representing the heap heap_size: Current size of the heap (indices 0 to heap_size-1) root_index: Index of the node to heapify from """ current = root_index while True: largest = current left = 2 * current + 1 right = 2 * current + 2 # Compare with left child if left < heap_size and arr[left] > arr[largest]: largest = left # Compare with right child if right < heap_size and arr[right] > arr[largest]: largest = right # If current is largest, heap property is satisfied if largest == current: return # Swap and continue heapifying arr[current], arr[largest] = arr[largest], arr[current] current = largest # ============================================# Testing and Verification# ============================================def verify_sorted(arr: list) -> bool: """Verify array is sorted in ascending order.""" return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1)) def run_tests(): """Run comprehensive tests on heap sort.""" test_cases = [ [], # Empty array [1], # Single element [2, 1], # Two elements [4, 10, 3, 5, 1, 8, 7], # Example from earlier [1, 2, 3, 4, 5], # Already sorted [5, 4, 3, 2, 1], # Reverse sorted [3, 3, 3, 3, 3], # All equal [5, 1, 4, 2, 8, 0, 3, 7, 6, 9], # Random ] print("Heap Sort Test Results:") print("=" * 50) for tc in test_cases: original = tc.copy() heap_sort(tc) is_correct = verify_sorted(tc) status = "✓" if is_correct else "✗" print(f"{status} {original} -> {tc}") # Large random test import random large_array = [random.randint(0, 10000) for _ in range(10000)] expected = sorted(large_array) heap_sort(large_array) if large_array == expected: print(f"✓ Large array (10000 elements) sorted correctly") else: print(f"✗ Large array sort FAILED") if __name__ == "__main__": run_tests()Let's consolidate our understanding with a precise analysis of heap sort's behavior across different scenarios.
Time Complexity Analysis:
Best Case: O(n log n)
Unlike insertion sort (O(n) for sorted input) or quick sort (O(n log n) with good pivots), heap sort always performs the same amount of work:
Even if the input is already sorted, heap sort doesn't benefit.
Average Case: O(n log n)
For random inputs, the constants are similar to worst case. The heapify operations don't find shortcuts on average.
Worst Case: O(n log n)
This is heap sort's strength. Unlike quick sort's O(n²) worst case, heap sort's randomness-independent structure guarantees O(n log n) always.
Space Complexity: O(1)
Heap sort is truly in-place:
| Metric | Value | Notes |
|---|---|---|
| Best Case Time | O(n log n) | No adaptive behavior |
| Average Case Time | O(n log n) | Consistent performance |
| Worst Case Time | O(n log n) | No bad inputs exist |
| Space Complexity | O(1) | Strictly in-place |
| Comparisons (build heap) | ≤ 2n | Linear phase |
| Comparisons (extraction) | ≤ 2n log n | Dominant term |
| Swaps (total) | O(n log n) | Each heapify may swap log n times |
Comparison Count Analysis:
For build-heap:
For extraction phase:
The extraction phase dominates, giving ~2n log n comparisons total. This is higher than merge sort's ~n log n comparisons, contributing to heap sort's constant-factor slowness.
Heap sort is not stable. When extracting equal elements, their relative order may not be preserved. This is because the extraction process doesn't consider original positions—it only cares about values. For applications requiring stability, merge sort or a modified algorithm with tagged elements is needed.
Implementing heap sort correctly requires attention to several subtle details. Here are the most common mistakes and how to avoid them.
(n // 2) - 1, not n // 2. Getting this wrong means either skipping a node or processing a leaf.last_non_leaf DOWN to 0, not up. Going up violates the precondition that children are valid heaps.arr[i] with arr[parent] instead of arr[largest]. Pay attention to variable names.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
# =====================================================# Common Mistakes in Heap Sort Implementation# ===================================================== # MISTAKE 1: Wrong starting index for build-heapdef build_heap_wrong_start(arr): n = len(arr) # WRONG: Starting at n // 2 instead of (n // 2) - 1 # This either skips the last non-leaf or processes a leaf for i in range(n // 2, -1, -1): # Bug! heapify(arr, n, i) def build_heap_correct(arr): n = len(arr) # CORRECT: Start at (n // 2) - 1 for i in range((n // 2) - 1, -1, -1): heapify(arr, n, i) # MISTAKE 2: Wrong direction in build-heap loopdef build_heap_wrong_direction(arr): n = len(arr) # WRONG: Going from 0 to last_non_leaf # Children are NOT valid heaps when we heapify their parent for i in range(0, n // 2): # Bug! heapify(arr, n, i) def build_heap_correct_direction(arr): n = len(arr) # CORRECT: Going from last_non_leaf DOWN to 0 for i in range((n // 2) - 1, -1, -1): heapify(arr, n, i) # MISTAKE 3: Not reducing heap size in extractiondef heap_sort_wrong_size(arr): n = len(arr) build_heap_correct(arr) for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # WRONG: Using n instead of i # This re-heapifies already-sorted elements heapify(arr, n, 0) # Bug! def heap_sort_correct_size(arr): n = len(arr) build_heap_correct(arr) for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # CORRECT: Use i as the current heap size heapify(arr, i, 0) # MISTAKE 4: Swapping with wrong child in heapifydef heapify_wrong_swap(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 # This is correct: finding the largest if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: # WRONG: Swapping with left instead of largest arr[i], arr[left] = arr[left], arr[i] # Bug! heapify_wrong_swap(arr, n, left) # Wrong index too def heapify_correct_swap(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: # CORRECT: Swap with largest, recurse on largest arr[i], arr[largest] = arr[largest], arr[i] heapify_correct_swap(arr, n, largest)When debugging heap sort, print the array after each heapify during build-heap, and after each extraction during the sorting phase. You should see: (1) a valid heap after build-heap (every parent ≥ children), and (2) the sorted portion growing from the right after each extraction.
We've now fully explored the two-phase structure of heap sort. Let's consolidate the key insights:
Looking Ahead:
In the next page, we'll analyze heap sort's time complexity more rigorously, understanding exactly why O(n log n) is guaranteed in all cases. We'll explore the constant factors, compare with other sorting algorithms, and understand the practical implications of heap sort's performance characteristics.
You now understand the complete mechanics of heap sort: the O(n) build-heap phase and the O(n log n) extraction phase. You can implement heap sort correctly and understand the subtle invariants that make it work. Next, we'll dive deeper into why heap sort achieves its guaranteed performance bounds.