Rank the top results with a heap
Continues from the last build: a trie that returns every matching completion unranked, no matter how many there are
Rung 5 gave the engine a trie that answers "what starts with this prefix" instantly, but it hands back every match it finds, in whatever order the trie happened to visit them, potentially hundreds of completions for a two-letter prefix, unranked and unusable as a dropdown.
What you'll build
By the end, top_k_by_score(candidates, k) returns exactly the k highest-scoring completions, correctly ordered even when scores tie, in roughly O(n log k) instead of O(n log n), verified against a sort-based baseline and a real benchmark across n = 2,000 / 20,000 / 200,000 that shows the speedup widening as n grows. The CLI's --top flag prints ranked, scored results instead of an unordered dump.
See how we teach, before you sign up
You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:
from __future__ import annotations
from typing import Generic, TypeVar, List
T = TypeVar("T")
class MinHeap(Generic[T]):
"""Array-backed binary min-heap. heap[0] is always the smallest item."""
def __init__(self) -> None:
self._data: List[T] = []
def __len__(self) -> int:
return len(self._data)
def peek(self) -> T:
if not self._data:
raise IndexError("peek from empty heap")
return self._data[0]
def push(self, item: T) -> None:
# TODO: append the item, then sift it up while smaller than its parent
raise NotImplementedError
def pop(self) -> T:
# TODO: swap root with the last item, remove it, sift the new root down
raise NotImplementedError
def _sift_up(self, i: int) -> None:
# TODO: walk toward the root, swapping while data[i] < data[parent]
raise NotImplementedError
def _sift_down(self, i: int) -> None:
# TODO: find the SMALLER of the two children, swap down until in place
raise NotImplementedError
Reading this file
def push(self, item: T) -> None:Starter stub, you fill in the append plus sift-up.def _sift_down(self, i: int) -> None:This is the one that needs to check both children, not just left.raise IndexError("peek from empty heap")Given for free, peek is the easy read-only part.class MinHeap(Generic[T]):Array-backed heap, generic so it can hold ScoredTerm objects.
Array-backed min-heap skeleton. peek() is given; push/pop/sift-up/sift-down are yours.
That's 1 of 9 explained code blocks in this single project.
The build, milestone by milestone
- 1
Build a min-heap from scratch
4 guided stepsRung 5's trie hands back every completion under a prefix in whatever order the trie happened to visit them. Ranking by score means you need a structure that always knows "what's currently weakest" without re-scanning everything. A binary heap keeps that answer at index 0 in O(1) and can update it in O(log n).
- 2
Score candidates and select top-k with a size-k min-heap
4 guided stepsThe trie from rung 5 might hand back thousands of completions for a short prefix. You don't need all of them sorted, you need the best 5. Keeping a min-heap of exactly k items means the heap only ever holds k things (O(k) memory) and every candidate does at most one comparison plus maybe one O(log k) swap, giving O(n log k) total instead of O(n log n).
- 3
Contrast with sort-everything, the baseline you're outgrowing
4 guided steps"Just sort it and take the first k" is the first idea everyone reaches for, and it isn't wrong, it's just doing more work than the question asked. This milestone measures exactly how much extra that habit costs once n grows and k stays small.
- 4
Benchmark top-k across a growing n
4 guided stepsBig-O reasoning says O(n log k) beats O(n log n) once k is much smaller than n, but "the math says so" isn't a benchmark. This milestone is where you actually watch the gap widen as n grows from thousands to hundreds of thousands, the same discipline every earlier rung used before trusting a complexity claim.
- 5
Wire heap-based ranking into the autocomplete CLI
4 guided stepsEverything so far has been a function you can unit test in isolation. This milestone is where a real query typed into the CLI actually comes back ranked, so the app you're carrying forward genuinely behaves differently than rung 5's unranked dump.
- 6
Handle ties and the k=0 / k>n edges cleanly
4 guided stepsA ranking function that returns different orders for the same input depending on insertion order will make results feel random to a user typing the same query twice. Later benchmarking work has to trust that a rerun is comparing apples to apples, which needs this determinism.
What's inside when you start
You'll walk away with
This is portfolio-grade. Build it free.
Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.
Start building