Sorting

Heap Sort

TimeO(n log n) SpaceO(1)

Imagine a tournament bracket. The best player rises to the top. You remove the champion, let the remaining players re-compete (the next best rises), and repeat. After all rounds, you have players ranked from best to worst.

When to use it: You need guaranteed O(n log n) with O(1) extra space. Unlike merge sort (needs O(n) space) or quick sort (has O(n^2) worst case), heap sort gives you both guarantees.

Key insight: A max-heap lets you extract the largest element in O(log n). Do this n times and you have a sorted array — all in-place by swapping the root with the last unsorted element.

Common trap: Heap sort is not stable — equal elements may change their relative order. If stability matters, use merge sort instead.

function heapSort(arr):
    n = length(arr)

    # Build max-heap (start from last non-leaf node)
    for i = n/2 - 1 down to 0:
        heapify(arr, n, i)

    # Extract elements one by one
    for i = n - 1 down to 1:
        swap(arr[0], arr[i])        # move current max to end
        heapify(arr, i, 0)          # restore heap on reduced array

function heapify(arr, heapSize, root):
    largest = root
    left = 2 * root + 1
    right = 2 * root + 2

    if left < heapSize and arr[left] > arr[largest]:
        largest = left
    if right < heapSize and arr[right] > arr[largest]:
        largest = right

    if largest != root:
        swap(arr[root], arr[largest])
        heapify(arr, heapSize, largest)   # recurse on affected subtree

def heap_sort(arr: list[int]) -> None:
    """Sort array in-place using heap sort."""
    n = len(arr)

    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)


def heapify(arr: list[int], heap_size: int, root: int) -> None:
    largest = root
    left = 2 * root + 1
    right = 2 * root + 2

    if left < heap_size and arr[left] > arr[largest]:
        largest = left
    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, heap_size, largest)

Problem: Sort an array in-place with guaranteed O(n log n) worst-case time and no extra memory allocation.

How would you approach this?

Answer: This is heap sort because it provides O(n log n) worst-case time (unlike quick sort) and O(1) extra space (unlike merge sort). Build a max-heap, then repeatedly swap the root with the last element and re-heapify.

Problem: Find the k largest elements in an unsorted array.

How would you approach this?

Answer: Use a min-heap of size k. Iterate through the array, pushing each element onto the heap. If the heap exceeds size k, pop the minimum. At the end, the heap contains the k largest elements. Time: O(n log k).

Time: O(n log n) in all cases. Building the heap is O(n) (not O(n log n) — each heapify is proportional to node depth, and most nodes are near the bottom). Extracting all n elements costs O(n log n) since each extraction requires O(log n) heapify.

Space: O(1) because the heap is built in-place within the input array. The only extra memory is a few index variables. Recursive heapify uses O(log n) stack space, but an iterative version achieves true O(1).