04 — Heaps, Priority Scheduling & Tries

At a glance

After completing this lesson you can:

• Implement priority scheduling and top-K analytics using binary heaps (heapq).
• Build prefix trees (Tries) for fast prefix autocompletion and route dispatching.
• Prevent sorting an entire dataset ($O(n \log n)$) when only top-$k$ elements ($O(n \log k)$) are needed.

Time: ~50 minutes · Prerequisites: 03 — Stacks, Queues & Ring Buffers

Reading Companion

• Book: Grokking Algorithms (2nd Edition) — Aditya Y. Bhargava
• Chapter 9: Dijkstra's Algorithm (Priority Queues, Weighted Graphs).

Why this matters in production

If an analytics endpoint calculates the "Top 10 slowest API endpoints" or "Top 5 most active tenants" across 1,000,000 requests by calling sorted(requests)[-10:], it wastes memory and CPU sorting 999,990 irrelevant items. Using a min-heap of size $k=10$ scales at $O(n \log k)$ time and $O(k)$ memory. Similarly, API routers (like FastAPI / Starlette routing tables) use Tries/Radix trees to match path prefixes (/api/v1/users/{id}) in $O(L)$ time (where $L$ is path length), independent of total route count.

Deep dive

1. Binary Min-Heaps (heapq)

A binary heap is a complete binary tree where each parent node is $\le$ its children (min-heap invariant):

• In Python, heapq represents the heap inside a standard list:
• Parent index $i

ightarrow$ Children at $2i + 1$ and $2i + 2$.

• Insert (heappush): $O(\log k)$.
• Pop min (heappop): $O(\log k)$.
• Look at min (h[0]): $O(1)$.

2. Prefix Trees (Tries)

A Trie organizes strings by character transitions:

Root
 ├── 'a' ── 'p' ── 'i' (endpoint)
 │                  └── '/' ── 'v' ── '1' (endpoint)
 └── 'h' ── 'e' ── 'a' ── 'l' ── 't' ── 'h' (endpoint)

Lookup time is $O(L)$, where $L$ is the string length, completely independent of how many millions of words or routes exist in the system.

Hands on

python3 phase1-cs-and-architecture/01-data-structures/04-heaps-trees-and-tries/examples/01_demo.py
python3 phase1-cs-and-architecture/01-data-structures/04-heaps-trees-and-tries/examples/02_trap.py

AI Trap & Code Review

# BAD AI-GENERATED CODE — O(N log N) FULL SORT FOR TOP-K
def get_top_k_slowest(requests: list[dict], k: int) -> list[dict]:
    # Sorts all 1,000,000 items in memory!
    return sorted(requests, key=lambda r: r["latency_ms"], reverse=True)[:k]

Exercises

1. Rung 1 (top_k_elements_heap): Given an iterable of numbers, return the top $k$ largest elements in descending order using heapq in $O(n \log k)$ time.
2. Rung 2 (PriorityJobQueue — Fix the AI Bug): Build a thread-safe priority task queue where jobs with lower priority numbers execute first, breaking ties deterministically by submission order.
3. Rung 3 (PrefixTrie): Implement insert(word) and starts_with(prefix) -> bool using nested dictionary nodes.
4. Rung 4 (PathRouterTrie): Build a prefix-based URL routing trie that matches paths like /api/v1/users to handler functions.
5. Rung 5 (SlidingWindowMedian): Compute rolling medians over a stream using two balancing heaps (max-heap for lower half, min-heap for upper half) in $O(\log k)$ per element.

Wrapping up

Can you explain?

1. Why is a size-$k$ min-heap used to find the top-$k$ largest items?
2. How does a Trie achieve $O(L)$ prefix matching regardless of dictionary size?
3. What is the heapify operation and what is its time complexity?

Further Reading & References

• CPython Source: listobject.c (Dynamic Array Implementation)
• Raymond Hettinger: Modern Dictionaries by Key-Sharing
• Alex Xu: System Design Interview — Rate Limiter Design
• Tim Roughgarden: Algorithms Illuminated Series