Day 30 · The triage nurse & the autocomplete tree

Heaps, Priority Queues & Tries

You will be able to

Explain the heap property and why a heap lives happily inside a plain list
Trace push and pop (sift-up / sift-down) by hand and state their O(log n) cost
Use heapq for top-K problems and justify the O(n log k) pattern
Implement a trie with insert, search, and prefix lookup
Choose between heap, trie, sorted list, and dict for a given access pattern

Today's ~120 minutes

Spaced-rep warm-up: due cards (trees, hashing)	10 min
ELI5 + tech read; watch heap push/pop in the visualizer	18 min
Guided: hand-built heap, two classics, working trie	42 min
Practice: ranked autocomplete	20 min
Project: log triage with heaps + trie, commit	20 min
Quiz + flashcards	10 min

Builds on: Day 29 — Binary trees & BSTs · Day 23 — Arrays & hashing · Day 22 — Big O & complexity

The analogy

🧸 ELI5⚙ Tech

An emergency room does not treat patients in arrival order — a triage nurse keeps the queue arranged so the most urgent case is always at the front. That is a priority queue, and the heap is the nurse's filing trick: not fully sorted (sorting everyone constantly would waste time nobody has), just organized enough that the most urgent patient is always instantly on top, and re-organizing after any arrival or discharge takes only a few swaps.

The trie is a different beast: the autocomplete tree. Imagine a tree where each branch is a LETTER. To store "cat", you walk c → a → t and plant a flag at the end. "car" shares the c → a corridor and branches at the last step. Now "every word starting with ca-" is not a search at all — you walk two steps and everything below you is the answer. The heap answers "who is most urgent right now?"; the trie answers "what starts with this?" Both answer their one question absurdly fast, and both are terrible at the other's question — choosing the structure that matches the question is the actual skill.

Why this matters on the job

Priority queues run the world you are heading into: OS schedulers (Day 39) pick the next process from one, task queues process urgent jobs first (Day 47), and "top-K" is the shape of half of production analytics — top 10 errors, top 5 slowest endpoints, k most similar embeddings. When you meet vector search on Day 115, the k-nearest-neighbor engine keeps its candidate set in a heap. Tries power autocomplete, spell-check, and — surprisingly — the token vocabulary lookups inside LLM tokenizers you will study on Day 96. In interviews, "kth largest" and "top-k frequent" are near-guaranteed encounters.

Watch it happen

The triage nurse — min-heap push and pop

step 1 / 7

A min-heap stored as an array: parent at i, children at 2i+1 and 2i+2. One rule — every parent ≤ its children. The minimum is ALWAYS at index 0, no searching.index 0 is the front of the triage line

🎯 Predict modespeed1×

Guided practice

guided 1

Build a heap by hand, then trust heapq

20 min

Create heaps_lab.py. Implement sift_up and sift_down for a list-based min-heap using the index arithmetic (children 2i+1 / 2i+2, parent (i-1)//2). The starter gives push and pop built on them.
Push 10 random numbers, popping all — verify they come out sorted (this is heapsort in disguise).
Draw the heap [1, 3, 2, 8, 5, 4] as a tree on paper. Push 0 and write each swap sift-up makes. Then verify with your code by printing the list after the push.
Redo the same operations with heapq and confirm identical list states — your implementation IS heapq's algorithm.
Max-heap detour: use heapq to pop the LARGEST of [7, 2, 9, 4] by negating on push and pop.

🐍 python — editable, runs in your browser

import heapq
import random

def sift_up(h, i):
    while i > 0:
        parent = (i - 1) // 2
        if h[i] < h[parent]:
            h[i], h[parent] = h[parent], h[i]
            i = parent
        else:
            break

def sift_down(h, i):
    n = len(h)
    while True:
        left, right, smallest = 2 * i + 1, 2 * i + 2, i
        if left < n and h[left] < h[smallest]:
            smallest = left
        if right < n and h[right] < h[smallest]:
            smallest = right
        if smallest == i:
            break
        h[i], h[smallest] = h[smallest], h[i]
        i = smallest

def push(h, x):
    h.append(x)
    sift_up(h, len(h) - 1)

def pop(h):
    h[0], h[-1] = h[-1], h[0]
    top = h.pop()
    if h:
        sift_down(h, 0)
    return top

mine, ref = [], []
values = [random.randint(0, 99) for _ in range(10)]
for v in values:
    push(mine, v)
    heapq.heappush(ref, v)
assert mine == ref, "same algorithm, same list layout"
print("popped:", [pop(mine) for _ in range(len(mine))])  # sorted!

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

Two classics + a working trie

22 min

Classic 1 — Kth largest element. Think aloud: "Sorting is O(n log n) and wasteful — I only care about k survivors. Min-heap of size k: anything smaller than the heap's minimum can never be top-k, so pop it." Implement kth_largest(nums, k) and test against sorted(nums)[-k].
Classic 2 — Top-k frequent elements. Think aloud: "Two structures, one per question: a Counter (Day 23) answers HOW OFTEN, a heap answers WHICH k. Push (count, item) tuples, keep size k." Implement and test on a word list.
Implement the Trie class in the starter: insert, search (whole word), starts_with (prefix). Each is a loop over characters walking child dicts.
Load the starter's mini word list and implement autocomplete(prefix): walk to the prefix node, then DFS (Day 29's traversal!) collecting every flagged word below it.

🐍 python — editable, runs in your browser

import heapq
from collections import Counter

def kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)     # evict the smallest survivor
    return heap[0]                  # min of the top k = kth largest

def top_k_frequent(items, k):
    counts = Counter(items)
    heap = []
    for item, c in counts.items():
        heapq.heappush(heap, (c, item))
        if len(heap) > k:
            heapq.heappop(heap)
    return [item for c, item in sorted(heap, reverse=True)]

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

def starts_with(self, prefix):
        return self._walk(prefix) is not None

t = Trie()
for w in ["cat", "car", "card", "care", "dog"]:
    t.insert(w)
print(t.search("car"), t.search("ca"), t.starts_with("ca"))  # True False True

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

Autocomplete, ranked

20 min

Combine both structures: build suggest(prefix, k) that returns the k MOST FREQUENT words matching a prefix, given a list of (word, frequency) pairs. Load the starter word list from guided (invent frequencies), and make suggest("ca", 2) return the two most-searched ca- words.

Constraints: trie for the prefix walk, heap for the top-k — no sorting the full candidate list. State the complexity in terms of prefix length L, matches m, and k.

Hints: store frequency on the trie's end-of-word nodes. Collect matches with the DFS from guided, then run the size-k heap over them: O(L + m log k).

Ship before you stop

Log triage: top-K everything

Revisit the Day 14 log analyzer with today's tools. Write dsa/topk_logs.py: stream the provided server log (or your Day 14 sample) and report the top 5 error messages, top 5 IPs, and top 3 slowest endpoints — all via the size-k heap pattern, never a full sort. Add a --prefix flag that autocompletes endpoint paths using a trie built from the log (so --prefix /api/u lists matching endpoints with hit counts). Commit with tests covering ties and k larger than the number of distinct items.

Rubric — check what you completed (0/5)

Top-K uses a bounded heap (never sorts all distinct items); the heap never exceeds size kHandles k larger than the number of distinct values without crashingTrie-backed --prefix flag returns all matching endpoints with countsComplexity of each report stated in comments (O(n log k) etc.)Tests cover a tie in counts and an empty log; committed to the practice repo

Common mistakes & misconceptions

Sorting the whole array to get the top k. The size-k min-heap gives O(n log k) — state the improvement out loud in interviews.
Reaching for a MIN-heap of size k but popping the max, or vice versa. To keep the k LARGEST you evict the smallest — that is why the heap is a min-heap.
Assuming the heap list is sorted. Only index 0 is special; h[1] is not the second-smallest. Pop repeatedly to consume in order.
Forgetting heapq is min-only. Max-heap = push negatives, or push (-priority, item) tuples.
Heapify confusion: heapq.heapify is O(n), not O(n log n) — a favorite interview follow-up.
Trie node with a fixed 26-slot array when a dict of children handles any alphabet (unicode, digits, "/" in URL paths) for free in Python.

Knowledge check

Q1. You need the 10 largest of 10 million numbers. Best approach and complexity?

Q2. In a list-based heap, where are the children of the node at index i?

Q3. Lookup cost for a word of length L in a trie holding one million words?

Go deeper — curated resources

toolVisuAlgo — Binary Heap visualization ↗15 min docsheapq — official Python docs (theory notes at the bottom are gold) ↗20 min bookOpenDSA — Heaps & Priority Queues chapter ↗20 min

If you have a third hour

Radix trees & path compression — Real routers and tokenizers compress single-child trie chains into one edge. Read about radix/PATRICIA trees and connect them to URL routing in FastAPI (Day 41).

Done means

Hand-rolled heap matches heapq state after identical operations
kth-largest and top-k-frequent pass tests against a sorted-reference oracle
Trie supports insert/search/starts_with; ranked autocomplete works
Log-triage project committed with tie and small-k tests green
Quiz ≥ 2/3

How this connects

← Back: The heap is Day 29's complete binary tree flattened into Day 23's array; the trie is Day 29's tree whose edges are Day 23's dict lookups. Top-k-frequent chains Day 23's Counter into today's heap.

Forward →: Day 31's Dijkstra-flavored ideas and Day 39's OS scheduler both run on priority queues. Day 96's tokenizers do trie-like longest-prefix matching, and Day 115's k-nearest-neighbor search keeps candidates in exactly today's bounded heap.