Heap Sort

Heap sort is selection sort with a better data structure: instead of scanning for the maximum each time, it keeps the unsorted part in a binary max-heap, so the maximum is always at the root and can be removed in O(log n). It sorts in place in O(n log n) even in the worst case. Interviewers ask it as "implement a sort with O(1) extra space and guaranteed O(n log n)", and its building blocks, sift-down and heapify, are what every priority-queue question relies on.

Intuition

• A heap is an array. Store a complete binary tree level by level: the children of index i are 2i + 1 and 2i + 2, and its parent is (i - 1) // 2. No pointers are needed.
• Max-heap property: every parent is at least as large as its children, so the largest element sits at index 0.
• Sift-down repairs one violation at index i: swap the element with its larger child until it is at least as large as both children or reaches a leaf. Cost: O(height) = O(log n).
• Heapify bottom-up: leaves are already heaps, so call sift-down on every internal node from the last parent n // 2 - 1 back to the root. This costs O(n), not O(n log n): about half the nodes are leaves (no work), a quarter sift at most one level, an eighth at most two, and the sum n/4 * 1 + n/8 * 2 + n/16 * 3 + ... is below n.
• Sort: swap the root (the maximum) with the last element of the heap, shrink the heap by one, and sift the new root down. After n - 1 rounds the array is sorted in ascending order.

When to use it in interviews / OAs

• "Sort in place with a worst-case guarantee": heap sort is O(n log n) worst case with O(1) extra space; quicksort is only O(n log n) on average and merge sort needs O(n) memory.
• "Implement heapify / sift-down / a priority queue from scratch".
• Partial sorting: after an O(n) heapify, k pops give the k largest (or smallest) elements in O(n + k log n).
• Nearly sorted data: if every element is at most k places from its final position, a min-heap of size k + 1 sorts it in O(n log k).
• Explaining library behavior: C++ std::sort (introsort) switches to heap sort when quicksort recursion gets too deep; std::partial_sort is heap-based.

Template

Sift-down and in-place heap sort

def sift_down(a: list, i: int, size: int) -> None:
    """Move a[i] down until the max-heap property holds within a[:size]."""
    while True:
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest


def build_max_heap(a: list) -> None:
    for i in range(len(a) // 2 - 1, -1, -1):  # last parent down to the root
        sift_down(a, i, len(a))


def heap_sort(a: list) -> None:
    build_max_heap(a)
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]  # move the current maximum to its final slot
        sift_down(a, 0, end)          # the heap now occupies a[:end]

The same idea with heapq: sorting a k-sorted array

Python's heapq is a min-heap on a plain list (heapify is O(n), heappush and heappop are O(log n)). When every element is at most k positions away from where it belongs, the smallest remaining element is always among the next k + 1 candidates:

import heapq


def sort_k_sorted(a: list[int], k: int) -> list[int]:
    heap = a[:k + 1]
    heapq.heapify(heap)
    out = []
    for x in a[k + 1:]:
        out.append(heapq.heappushpop(heap, x))  # push the new element, pop the minimum
    while heap:
        out.append(heapq.heappop(heap))
    return out

For a max-heap with heapq, push negated values (-x) or tuples like (-priority, counter, item).

Complexity

• Build heap: O(n). Each of the n - 1 extractions: O(log n). Total O(n log n) in the best, average and worst case (it is O(n) only in degenerate cases such as all-equal keys).
• Space: O(1) extra; the heap lives inside the input array.
• Not stable: the long-distance swap of the root with the last element reorders equal keys.
• In practice heap sort is usually slower than a good quicksort because its memory accesses jump around the array and defeat CPU caches.
• sort_k_sorted: O(n log k) time, O(k) extra space.

Common pitfalls

• Heapifying top-down with sift-down. Sift-down assumes both subtrees are already heaps, so iterate from the last parent back to index 0.
• Comparing with the wrong child. Swap with the larger child (in a max-heap), otherwise the larger child ends up below a smaller parent.
• Forgetting to shrink the heap. After swapping the root to position end, sift down within a[:end], not the whole array.
• Index formulas for 1-based arrays. With a 1-based layout the children are 2i and 2i + 1; do not mix the two conventions.
• heapq is a min-heap. Negate keys for max-heap behavior, and add a tie-breaking counter when payloads are not comparable (two dicts with equal priority raise a TypeError).
• Calling heap sort stable. It is not.

Interview variations

• Kth largest element: keep a min-heap of size k (O(n log k)), or heapify and pop k times (O(n + k log n)).
• Merge k sorted lists: a min-heap holds the current head of each list.
• Top k frequent elements and k closest points: a heap of size k keyed by frequency or distance.
• Find the median of a data stream: a max-heap for the lower half and a min-heap for the upper half.
• Last stone weight and similar "repeatedly take the two largest" simulations: a max-heap via negation.
• Why is bottom-up heapify O(n)? A favorite follow-up: most nodes are near the bottom, where sift-down is cheap.