🏆 Heap Sort

Intermediate ~15 min read

You're organizing a knockout tournament with hundreds of players. You need to find the champion, then the runner-up, then third place, and so on. The smart way: Build a tournament bracket (max heap) where the strongest always rises to the top. Extract the champion, reorganize, repeat. That's Heap Sort!

The Tournament Organizer

Imagine a tournament tree where every parent is stronger than their children. The root? That's always the champion!

The Strategy

Build a max heap: Organize players so strongest is at top
Extract the champion: Take the root (maximum element)
Reorganize: Heapify the remaining players
Repeat: Until everyone is ranked

Key insight: The heap always keeps the maximum at the root! Each extraction takes O(log n) time.

What is a Heap?

Heap Data Structure

A heap is a complete binary tree with a special property:

Max Heap: Every parent ≥ its children (root is maximum)
Min Heap: Every parent ≤ its children (root is minimum)
Complete: All levels filled except possibly the last, which fills left-to-right

For Heap Sort, we use a max heap!

Array Representation - The Magic!

Here's the beautiful part: We don't need pointers! A heap can be stored in an array:

Array Index Formulas

For an element at index i:

Left child: 2i + 1
Right child: 2i + 2
Parent: (i - 1) / 2

Example: Element at index 1 has children at indices 3 and 4, parent at index 0.

See It in Action

Watch how Heap Sort builds a max heap, then extracts elements one by one:

Understanding the Process

🟡 Yellow (Current): Node being heapified
🟣 Purple (Comparing): Comparing with children
🟠 Orange (Swapping): Elements being swapped
🟢 Green (Sorted): Extracted from heap, in final position
Phase 1: Build max heap - O(n)
Phase 2: Extract max n times - O(n log n)
Total: O(n) + O(n log n) = O(n log n)

The Code

"""
Heap Sort - The Tournament Organizer
Build a max heap, then extract champions one by one!
"""

def heap_sort(arr):
    """
    Heap Sort: O(n log n) guaranteed, O(1) space
    1. Build max heap from array
    2. Extract max repeatedly, placing at end
    """
    n = len(arr)
    print(f"Original array: {arr}")
    print(f"\n{'='*60}")
    print("PHASE 1: Building Max Heap")
    print(f"{'='*60}")
    
    # Build max heap (rearrange array)
    build_max_heap(arr, n)
    
    print(f"\n{'='*60}")
    print("PHASE 2: Extracting Max and Sorting")
    print(f"{'='*60}\n")
    
    # Extract elements from heap one by one
    for i in range(n - 1, 0, -1):
        # Move current root (max) to end
        arr[0], arr[i] = arr[i], arr[0]
        print(f"Extracted max {arr[i]}, placed at index {i}")
        print(f"Array: {arr}")
        
        # Heapify the reduced heap
        heapify(arr, i, 0)
        print(f"After heapify: {arr}\n")
    
    return arr

def build_max_heap(arr, n):
    """
    Build max heap from unsorted array
    Start from last non-leaf node and heapify each
    Time: O(n) - surprisingly not O(n log n)!
    """
    # Index of last non-leaf node
    start_idx = n // 2 - 1
    
    print(f"Starting from last non-leaf node at index {start_idx}")
    
    # Perform reverse level order traversal
    for i in range(start_idx, -1, -1):
        print(f"\nHeapifying subtree rooted at index {i} (value: {arr[i]})")
        heapify(arr, n, i)
        print(f"After heapifying index {i}: {arr}")
    
    print(f"\n✓ Max heap built! Root (max): {arr[0]}")

def heapify(arr, n, i):
    """
    Heapify subtree rooted at index i
    Ensures max heap property: parent >= children
    Time: O(log n)
    """
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child
    
    # Check if left child exists and is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # Check if right child exists and is greater than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # If largest is not root, swap and continue heapifying
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        print(f"  Swapped {arr[largest]} ↔ {arr[i]} (indices {largest} ↔ {i})")
        
        # Recursively heapify the affected subtree
        heapify(arr, n, largest)

def print_heap_as_tree(arr):
    """Visualize array as binary tree"""
    n = len(arr)
    if n == 0:
        return
    
    print("\nHeap as Tree:")
    level = 0
    i = 0
    while i < n:
        level_size = 2 ** level
        level_elements = arr[i:min(i + level_size, n)]
        
        # Print with indentation
        indent = " " * (4 * (3 - level)) if level < 3 else ""
        print(f"{indent}Level {level}: {level_elements}")
        
        i += level_size
        level += 1

# Example 1: Basic heap sort
print("=" * 60)
print("Example 1: Basic Heap Sort")
print("=" * 60)
arr1 = [12, 11, 13, 5, 6, 7]
print(f"Original: {arr1}")
print_heap_as_tree(arr1)

result1 = heap_sort(arr1.copy())
print(f"\n{'='*60}")
print(f"Final sorted array: {result1}")
print(f"{'='*60}\n")

# Example 2: Already sorted (still O(n log n))
print("\n" + "=" * 60)
print("Example 2: Already Sorted")
print("=" * 60)
arr2 = [1, 2, 3, 4, 5]
result2 = heap_sort(arr2.copy())
print(f"Sorted: {result2}\n")

# Example 3: Reverse sorted
print("=" * 60)
print("Example 3: Reverse Sorted")
print("=" * 60)
arr3 = [5, 4, 3, 2, 1]
result3 = heap_sort(arr3.copy())
print(f"Sorted: {result3}\n")

# Example 4: With duplicates
print("=" * 60)
print("Example 4: With Duplicates")
print("=" * 60)
arr4 = [4, 10, 3, 5, 1, 3, 10]
result4 = heap_sort(arr4.copy())
print(f"Sorted: {result4}\n")

print("=" * 60)
print("Key Insights:")
print("=" * 60)
print("✓ Build heap: O(n) - starts from bottom, most nodes sink little")
print("✓ Extract max: O(log n) × n times = O(n log n)")
print("✓ Total: O(n log n) guaranteed - no worst case!")
print("✓ Space: O(1) - in-place sorting")
print("✓ Not stable - equal elements may swap positions")
print("✓ Array representation: parent at i, children at 2i+1 and 2i+2")

Output

Click Run to execute your code

The Heapify Function: This is the core! It ensures the heap property by "sinking down" a node until it's in the right position. Compare with children, swap with the larger one, repeat.

Quick Quiz

Why does building a heap take O(n) and not O(n log n)?

Show answer
Surprising but true! Most nodes are near the bottom of the tree and only need to "sink down" a little. Only the root might sink all the way down. The math works out: sum of (nodes at level) × (distance to sink) = O(n). This is why we build bottom-up, not top-down!
How does Heap Sort achieve in-place sorting?

Show answer
As we extract the max (root), we swap it with the last element in the heap, then reduce the heap size by 1. The extracted element stays at the end of the array. The heap shrinks from the right, and the sorted portion grows from the right. Same array, no extra space needed!

Why O(n log n) Guaranteed?

Let's break down the complexity:

Operation	Time	Why
Build Max Heap	O(n)	Bottom-up heapify, most nodes sink little
Extract Max (once)	O(log n)	Heapify from root to leaf
Extract Max (n times)	O(n log n)	n extractions × O(log n) each
Total	O(n log n)	O(n) + O(n log n) = O(n log n)

✅ Guaranteed Performance!

Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n log n) ✓
Space: O(1) - in-place!

Unlike Quick Sort, Heap Sort has NO worst case degradation!

Heap Sort vs Others

How does Heap Sort compare to Merge Sort and Quick Sort?

Feature	Merge Sort	Quick Sort	Heap Sort
Strategy	"Split evenly, merge"	"Pivot, partition"	"Tournament bracket"
Best Case	O(n log n)	O(n log n)	O(n log n)
Worst Case	O(n log n) ✓	O(n²) ⚠️	O(n log n) ✓
Space	O(n) - needs extra array	O(log n) - recursion	O(1) - in-place ✓
Stable	Yes ✓	No	No
Cache Performance	Good	Excellent ✓	Fair
In Practice	"Predictable"	"Usually fastest" ✓	"Guaranteed + in-place"

The Verdict

Heap Sort is the "safe choice":

✅ Guaranteed O(n log n) (like Merge Sort)
✅ In-place with O(1) space (like Quick Sort)
✅ No worst case surprises
⚠️ Slower than Quick Sort in practice (cache misses)
⚠️ Not stable (equal elements may swap)

Best of both worlds: guaranteed performance + minimal space!

When to Use Heap Sort

✅ Use When:

Need guaranteed O(n log n): No worst case degradation
Limited memory: In-place with O(1) space
Can't afford worst case: Unlike Quick Sort
Building priority queue: Heap structure useful
Embedded systems: Predictable performance + low memory

❌ Avoid When:

Need stability: Heap Sort is unstable
Need fastest average: Quick Sort usually faster
Cache performance critical: Quick Sort better locality
Small arrays: Insertion Sort better

🎯 Real-World Use

Where Heap Sort shines:

Intro Sort: C++ std::sort uses Heap Sort as fallback when Quick Sort degrades
Priority Queues: Heap structure is perfect for this
Embedded Systems: Predictable performance + low memory
Real-time Systems: Guaranteed O(n log n) matters

Common Misconceptions

❌ Misconception 1: "Heap Sort is the fastest"

Reality: Quick Sort is usually faster in practice!

Quick Sort: Better cache locality (works on nearby elements)
Heap Sort: Jumps around array (parent/child not adjacent)
Cache misses: Make Heap Sort slower despite same O(n log n)
Benchmark: Quick Sort often 2-3x faster on modern CPUs

But: Heap Sort wins on guaranteed performance!

❌ Misconception 2: "Building a heap is O(n log n)"

Reality: It's O(n)! Surprisingly efficient!

Top-down: Insert n elements × O(log n) = O(n log n)
Bottom-up: Heapify from bottom = O(n) ✓
Why: Most nodes are near bottom, only sink a little
Math: Σ(nodes at level h) × h = O(n)

This is why we build bottom-up, not top-down!

❌ Misconception 3: "Heap Sort is stable"

Reality: No! Equal elements can change relative order.

Example: [3a, 3b, 1] → [1, 3b, 3a] (3b before 3a now!)
Why: Heapify doesn't preserve relative order
Swaps: Can move equal elements past each other
If need stable: Use Merge Sort instead

❌ Misconception 4: "Heaps are only for sorting"

Reality: Heaps have many other uses!

Priority Queues: OS task scheduling, event handling
Dijkstra's Algorithm: Shortest path finding
Huffman Coding: Data compression
Top K Elements: Find k largest/smallest efficiently
Median Maintenance: Running median with two heaps

Learning Heap Sort teaches you a versatile data structure!

💡 Key Takeaway

Heap Sort is the "safe choice" for sorting:

✅ Guaranteed O(n log n) - no worst case
✅ In-place O(1) space - minimal memory
✅ Teaches heap data structure - useful beyond sorting
⚠️ Slower than Quick Sort in practice - cache misses
⚠️ Not stable - can't preserve order of equals

Understanding Heap Sort teaches you about guaranteed performance, space efficiency, and the power of heap data structures!

Summary

The 3-Point Heap Sort Guide

Strategy: Build max heap (O(n)), extract max repeatedly (O(n log n)) - tournament bracket!
Complexity: O(n log n) guaranteed, O(1) space - best of Merge + Quick!
Trade-off: Guaranteed performance + minimal space vs cache performance

Interview tip: Mention Heap Sort for guaranteed O(n log n) with in-place sorting. Explain heap property and array representation. Compare with Merge Sort (space) and Quick Sort (worst case)!

What's Next?

You've mastered comparison-based O(n log n) sorts! Next: Counting Sort - breaking the O(n log n) barrier with linear-time sorting!

Practice: Implement a priority queue using a heap. Try finding the k largest elements in an array using a min heap!

Previous Quick Sort

Next Counting Sort