Skip to main content

Heapsort and the Heap-Based Priority Queue API

What This Concept Is​

Heapsort sorts in place by turning the array into a max-heap and then repeatedly swapping the root with the last element and re-sifting the reduced prefix:

def heapsort(A):
    n = len(A)
    build_max_heap(A)
    for i in range(n - 1, 0, -1):
        A[0], A[i] = A[i], A[0]
        sift_down(A, 0, i)

Analysis: build_max_heap costs (O(n)); (n - 1) extract-max operations each cost (O(\log n)); total (\Theta(n \log n)) worst case. It is in-place ((O(1)) auxiliary), not stable, and not adaptive -- presortedness does not help.

Priority queue (PQ) is the ADT with operations:

  • insert(x, key) -- add an element with priority key.
  • extract_min() (or extract_max()) -- remove and return the best-keyed element.
  • peek() -- best key without removing.
  • decrease_key(x, new_key) -- change the priority (requires a handle or index map).
  • merge(Q1, Q2) -- union two PQs (fast only in binomial/Fibonacci/pairing heaps).

The binary heap gives insert/extract in (O(\log n)), peek in (O(1)). Specialized variants buy different trade-offs: binomial heaps do (O(\log n)) merge; Fibonacci heaps achieve (O(1)) amortized decrease_key (critical for Dijkstra's theoretical bound); pairing heaps are simpler and empirically competitive; d-ary heaps trade shallow depth for wider fan-out.

Heapsort vs. quicksort vs. mergesort. Heapsort has the best worst-case-plus-memory profile: (O(n \log n)) worst-case and (O(1)) extra space. Quicksort is usually faster on random data due to cache locality but worst-case (\Theta(n^2)). Mergesort is stable and predictable but needs (\Theta(n)) auxiliary. Introsort (std::sort) picks quicksort, switches to heapsort when recursion depth threatens the worst case, and finishes with insertion sort on small subarrays.

Why It Matters Here​

Heapsort proves that (\Theta(n \log n)) worst-case sorting is achievable with (O(1)) extra memory -- mergesort cannot do that without severe gymnastics, and quicksort cannot at all. Heapsort is therefore the "worst-case-safe" backup inside introsort and pdqsort.

The priority-queue API, backed by a heap, is what Dijkstra's shortest path, Prim's MST, A*, Huffman coding, event-driven simulation, and top-K all use. Treating "priority queue" as a primitive with a known cost profile is how graph algorithms get clean analyses: counting heap ops replaces counting comparisons.

In practice, the API matters more than the implementation. Once you think "I need to always grab the best remaining thing, and the 'best remaining thing' changes as I work," you reach for a priority queue. Which heap variant powers it is secondary.

Concrete Examples​

Example 1 -- heapsort trace on [4, 10, 3, 5, 1].

Build max-heap (sift_down from index 1, then 0): [4,10,3,5,1] -> [4,10,3,5,1] (index 1 OK) -> [10,5,3,4,1] (index 0 swaps with 10, then 4 stays).

  • Swap A[0] and A[4] -> [1,5,3,4,10]; sift_down on prefix of length 4 -> [5,4,3,1,10].
  • Swap A[0] and A[3] -> [1,4,3,5,10]; sift_down on prefix of length 3 -> [4,1,3,5,10].
  • Swap A[0] and A[2] -> [3,1,4,5,10]; sift_down on prefix of length 2 -> [3,1,4,5,10].
  • Swap A[0] and A[1] -> [1,3,4,5,10]. Done.

Total: (O(n)) build + (n-1) sift_down of cost (O(\log n)) each.

Example 2 -- Dijkstra with a binary-heap PQ. On a graph of (V) vertices and (E) edges:

pq = MinHeap()
dist = {v: inf for v in V}; dist[start] = 0
pq.insert(start, 0)
while pq:
    u, d = pq.extract_min()
    if d > dist[u]:         # stale entry (lazy decrease_key)
        continue
    for v, w in neighbors(u):
        if d + w < dist[v]:
            dist[v] = d + w
            pq.insert(v, d + w)   # lazy: push a fresh entry

Every edge triggers at most one insert; every vertex is popped at most once as a fresh entry (other pops are stale). Total: (O((V + E) \log V)). With a Fibonacci heap and true decrease_key, this drops to (O(E + V \log V)) -- a tighter bound exploited in theory but rarely in practice because the Fibonacci-heap constants are large.

Common Confusion / Misconceptions​

"Heapsort is always better than quicksort because its worst case is (O(n \log n))." Not in practice. On random data and modern CPUs, quicksort usually wins 2-3x because of cache locality and branch prediction -- heapsort's sift_down jumps around the array. Heapsort wins only when worst-case guarantees matter (adversarial input, real-time, security-sensitive code paths).

"Iterating the heap array gives sorted output." No -- only repeated pops yield sorted order. The array itself is heap-ordered, not sorted. Students who print the heap array and see "almost sorted" are confusing the two.

"decrease_key is just a find-and-update." The heap does not know where a given key sits, so naive decrease-key is (\Theta(n)) just to find it. Two standard fixes: (a) maintain an external key -> heap index map updated on every swap; (b) lazy deletion -- push a fresh (new_priority, key) and filter stale entries on pop. Lazy is simpler but grows the heap; indexed is tighter but complicates every swap.

"A heap is a stable priority queue." Heaps are not stable -- equal-priority items can emerge in any order. For stable PQ semantics, embed a monotonically increasing tie-breaker: (priority, insertion_counter, value).

How To Use It​

For sorting:

  1. Prefer the language's default sort -- introsort/pdqsort/Timsort are faster and stable (Timsort).
  2. Reach for std::sort_heap / explicit heapsort only when you need (O(n \log n)) worst-case and (O(1)) extra memory with no dependencies.

For priority queue use:

  1. Decide min-heap vs. max-heap; if the library only offers one, negate keys for the other.
  2. For decrease_key, pick indexed heap (max performance) or lazy deletion (max simplicity); document your choice.
  3. For graph algorithms, count heap ops: (O((V + E) \log V)) with a binary heap; (O(E + V \log V)) with Fibonacci.
  4. For top-K, use heapq.nsmallest(k, data) / std::partial_sort -- a bounded heap beats a full sort when (k \ll n).
  5. For event simulation, key the heap by (timestamp, tie_break, event) to keep determinism across equal timestamps.

Transfer / Where This Shows Up Later​

  • S2 M2 (this module). Concept 16 specializes the PQ API to simulation, Dijkstra, top-K, and median maintenance.
  • S2 M3 (graphs). Dijkstra, Prim, and A* quote the (O((V + E) \log V)) bound from this concept; Fibonacci heaps appear in theoretical MST bounds (Gabow-Galil-Spencer-Tarjan).
  • S3 (software design). The PQ is the textbook ADT-vs-implementation example; the book's "prefer composition over inheritance" discussion of container adapters uses std::priority_queue as the archetype.
  • S4 (systems programming). Linux hrtimer wheels, Go's timer heap, and epoll's timeout queue are heap-based PQs; userspace schedulers like Tokio's JoinSet use the same pattern.
  • S5 (OS). Real-time schedulers (EDF, rate-monotonic) use heaps of deadlines; memory reclamation picks victim pages via a priority structure.
  • S6 (databases). ORDER BY ... LIMIT k uses a bounded heap in Postgres' Limit node; external merge sort's final phase is a k-way heap merge; LSM-tree compaction heaps cursors across SSTables.
  • S7 (architecture). Retry schedulers, token buckets, and rate-limiters reach for PQs keyed by earliest-allowed-time; ADRs specify the PQ SLA (bounded latency, stability).
  • S8 (system design). Load balancers (power-of-two-choices with a heap of loads), pub-sub queues with priorities (e.g., SQS priority polling), and consistent-hash repair queues all use PQs.

Check Yourself​

  1. Why is heapsort worst-case (\Theta(n \log n)) but often slower than quicksort in practice?
  2. Give the cost profile of a binary-heap priority queue for insert, extract_min, peek, and decrease_key.
  3. Why is naive decrease_key slow, and what are the two standard fixes?
  4. When is heapq.nsmallest(k, data) strictly better than sorted(data)[:k]?
  5. Why does introsort fall back to heapsort rather than, say, mergesort, when quicksort recursion is deep?

Mini Drill or Application​

  1. Trace heapsort on [8, 3, 7, 1, 5, 9, 2] and record the array after each outer iteration.
  2. Implement a priority queue supporting insert, extract_min, and decrease_key in (O(\log n)) using a heapq plus a key -> index dictionary. Write property-based tests.
  3. Explain why an event-driven simulator with (E) events on (V) entities runs in (O((E + V) \log V)) with a binary heap.
  4. Implement top-K over an unbounded stream using a bounded min-heap of size K; compare against sorted()[:k] for (n = 10^7, k = 100).
  5. Benchmark binary vs. 4-ary heap on Dijkstra over a road network; report speedup and a one-line cache-based explanation.

Read This Only If Stuck​