S029 · Heaps & Priority Queues

Module M03: Data Structures & Algorithms · Session 29 of 130 · Track: SW 🎋

What you'll be able to do after this session

• Explain Heaps & Priority Queues to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S028 — Trees & BSTs — Traversal (BFS/DFS)

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Heaps in 100 seconds (NeetCode) — priority queues in one sitting.
• 🎥 Deep dive (30–60 min) · MIT 6.006 — Heaps and Heap Sort (Erik Demaine) — the full derivation.
• 🎥 Hands-on demo (10–20 min) · Python heapq walkthrough (mCoding) — practical patterns you'll reuse forever.
• 📖 Canonical article · Python docs — heapq — the standard-library API and its gotchas.
• 📖 Book chapter / tutorial · Wikipedia — Binary heap — sift-up / sift-down explained cleanly.
• 📖 Engineering blog · Netflix — Introducing TimeSeries scalable event storage — priority-ordered data at scale.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: 'Give me the smallest/largest thing' in O(log n).

A heap is a binary tree with one simple rule: every parent is smaller than its children (min-heap) or larger (max-heap). It doesn't care about ordering within a level; it only guarantees that the smallest (or largest) element is always sitting at the root. That single property makes it a priority queue: you can peek at the "most important" item in O(1), and remove or insert in O(log n).

You already use priority queues all day: the OS's task scheduler picks the highest-priority runnable process. Dijkstra's shortest-path algorithm picks the nearest unvisited node. Event simulators pick the next event by timestamp. A hospital ER picks the sickest patient. Any time "always process the biggest / smallest / most urgent next" is the rule, a heap is the right structure.

Under the hood, a binary heap is stored in a flat array (no pointers!) using clever index math: the children of index i are at 2i+1 and 2i+2, and the parent is at (i-1)/2. This gives you tree structure with array cache locality — the best of both worlds.

One-sentence gotcha to carry forever: A heap is not a sorted array — the root is guaranteed smallest, but element at index 5 could be anywhere relative to element at index 6. Iterating a heap in order requires repeatedly popping the root, which is O(n log n) total (that's heapsort). If you need "the k smallest of n," a heap of size k gives you an elegant O(n log k) solution — better than sorting all n.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Min-heap stored as an array:

Values [1, 3, 6, 5, 9, 8] interpreted as a tree:

Every parent ≤ its children — the min-heap property holds. Root (index 0) = 1 = the minimum.

Worked example 1 — insert 2:

1. Add 2 at the end (index 6). Array: [1, 3, 6, 5, 9, 8, 2]. Tree: 2 is a child of 6.
2. Sift up: 2 < parent 6, swap. Array: [1, 3, 2, 5, 9, 8, 6].
3. 2 < parent 1? No. Stop. Heap property restored.

Total work: O(log n) swaps (height of the tree).

Worked example 2 — pop the min:

Heap: [1, 3, 2, 5, 9, 8, 6]. Root is 1.

1. Return 1. Move last element (6) to the root. Array: [6, 3, 2, 5, 9, 8].
2. Sift down: children of 6 are 3 and 2; smaller is 2. Swap 6 and 2. Array: [2, 3, 6, 5, 9, 8].
3. Children of 6 (now at index 2): 8. 6 < 8, stop.

Popped 1, heap restored in O(log n).

Top-K pattern — the reason heaps show up in every "find the K largest" problem:

To find the K largest items in a stream of n items:

• Maintain a min-heap of size K.
• For each new item: if heap has < K items, push. Otherwise if item > heap.min, replace the min.
• At the end, the heap contains the K largest, in unspecified order.

Time: O(n log K), space: O(K). Massively better than sorting all n (O(n log n) time, O(n) space) when K ≪ n.

API summary — Python's heapq module:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# heaps_playground.py
import heapq
from time import perf_counter
import random
 
# ---- 1. Basic min-heap ----
h = []
for x in [5, 3, 8, 1, 9, 2]:
    heapq.heappush(h, x)
 
print("heap internal :", h)         # note: NOT sorted
print("peek smallest :", h[0])
 
order = []
while h: order.append(heapq.heappop(h))
print("pop-all order :", order)     # sorted output
 
# ---- 2. heapify: O(n) construction from arbitrary list ----
arr = [random.randint(0, 100) for _ in range(10)]
heapq.heapify(arr)
print("
heapified:", arr, "min at [0]:", arr[0])
 
# ---- 3. Top-K pattern ----
def top_k_largest(stream, k):
    h = []
    for x in stream:
        if len(h) < k:
            heapq.heappush(h, x)
        elif x > h[0]:
            heapq.heapreplace(h, x)   # pop + push in one step
    return sorted(h, reverse=True)
 
data = [random.randint(0, 1_000_000) for _ in range(1_000_000)]
t0 = perf_counter(); topk = top_k_largest(data, 10); t1 = perf_counter()
t2 = perf_counter(); topk_sort = sorted(data)[-10:]; t3 = perf_counter()
print(f"
top-10 via heap  : {(t1-t0)*1000:.1f} ms -> {topk}")
print(f"top-10 via sort  : {(t3-t2)*1000:.1f} ms")
 
# ---- 4. Max-heap in Python (negate the values) ----
mh = []
for x in [5, 3, 8, 1, 9, 2]:
    heapq.heappush(mh, -x)
print("
max-heap peek:", -mh[0])
 
# ---- 5. Priority queue with (priority, item) tuples ----
tasks = []
heapq.heappush(tasks, (2, "write email"))
heapq.heappush(tasks, (1, "fix production bug"))
heapq.heappush(tasks, (3, "read a book"))
print("
Processing tasks in priority order:")
while tasks:
    prio, item = heapq.heappop(tasks)
    print(f"  [priority={prio}] {item}")
 
# ---- 6. Merge k sorted streams with a heap ----
def merge_k_sorted(lists):
    h = []
    for i, lst in enumerate(lists):
        if lst: heapq.heappush(h, (lst[0], i, 0))
    out = []
    while h:
        val, i, j = heapq.heappop(h)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(h, (lists[i][j+1], i, j+1))
    return out
 
print("
merge:", merge_k_sorted([[1,4,7],[2,5,8],[3,6,9]]))

Checklist:

1. h after all pushes is not sorted, but h[0] is always the smallest.
2. Pop-all order is sorted ascending.
3. top_k_largest on 1M items is dramatically faster than sorting the whole list.
4. Task processing prints "fix production bug" first, then "write email", then "read a book".
5. merge_k_sorted returns [1, 2, 3, 4, 5, 6, 7, 8, 9].

Try this modification: implement a MedianFinder class supporting add(num) and median() in O(log n) and O(1) respectively. Hint: use two heaps — a max-heap for the lower half, a min-heap for the upper half, and keep them balanced within 1 element of each other.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Heaps are quietly everywhere — the OS scheduler running your terminal right now is a heap-like structure ordering runnable processes by dynamic priority. Some concrete places they show up:

1. Kernel schedulers. Linux's CFS (Completely Fair Scheduler) uses a red-black tree ordered by "virtual runtime" — functionally a priority queue picking the process that has run least. Older schedulers used explicit heaps. Both share the "always pick the highest-priority runnable thing" pattern.

2. Dijkstra & A pathfinding.* Every routing engine — Google Maps, OSRM, video-game AI — uses a priority queue keyed by distance_so_far + heuristic. Google Maps at scale actually uses much fancier hierarchical structures (contraction hierarchies, transit-node routing), but the mental model is still "pop the most promising frontier node."

3. Discrete-event simulation. Network simulators (ns-3), circuit simulators, epidemic models — all keep a heap of (future_time, event) tuples, pop the next event, execute it, possibly enqueue new events. Millions of events per second, O(log n) per operation.

4. Top-K in analytics & search. "Top 10 trending topics on Twitter", "top 100 most-relevant search results", "top K frequent items in this hour of logs" — all classic top-K heap patterns. Search engines like Elasticsearch use bounded priority queues heavily during query execution: instead of scoring all matching docs, they maintain a heap of the top-K seen so far and prune anything worse than the current worst-of-K.

5. Rate limiting and delay queues. SQS delay queues, Redis sorted sets used as delay queues, and cron-like schedulers are priority queues keyed by "when to fire next."

Common bugs and gotchas:

• Trying to update an item's priority in place. Heaps don't support O(log n) decrease_key out of the box (you'd have to find the item first, which is O(n)). Standard trick: leave the stale entry, push a new one, and skip stale entries on pop (mark them via a companion set). This is exactly how production Dijkstra implementations handle it.
• Comparing incomparable items. heapq in Python breaks ties by comparing the second element of the tuple; if that's an object without __lt__, you'll crash. Fix: use (priority, counter, item) with a monotonically increasing counter as tie-breaker.
• Assuming heap iteration is sorted. for x in heap walks the underlying array, which is NOT sorted — a bug that only shows up in production with certain data patterns. Always heappop if you need sorted order.
• Unbounded priority queues. Same failure mode as unbounded regular queues: unbounded memory. Netflix's Zuul, Reddit's request queues — both have had incidents where a spike in slow requests made a "sort-by-arrival-time" priority queue balloon.

(e) Quiz + exercise · 10 min

1. What is the defining property of a min-heap?
2. Why is heapify(list) O(n) rather than O(n log n)?
3. Why does the "top K largest of a stream" pattern use a min-heap of size K, not a max-heap?
4. How would you build a max-heap using Python's heapq module (which is min-only)?
5. Give one algorithm and one production system that internally rely on a priority queue.

Stretch (connects to S030 — Graphs, coming next): Sketch Dijkstra's shortest-path algorithm. Where exactly in the algorithm does the priority queue appear, and what happens if you replace it with a plain FIFO queue?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Heaps & Priority Queues? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S030): Graphs — Representation, BFS, DFS, Shortest Path
• Previous (S028): Trees & BSTs — Traversal (BFS/DFS)
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.