Build an autocomplete

Is the board this build joins up. Its heap corner keeps the smallest number at the top and lists “top-K” among its uses; its trie corner spells “cat” and “car” down one shared path and says a trie is “perfect for AUTOCOMPLETE”. This lesson makes those two corners work as one machine.

Before you start. Clinic #23: Implement Trie built a trie: every stored word is a path from one starting node, one letter per step, words that begin alike share their start, and a flag marks the node where a word ends. Trees (BST, balancing, heaps, tries) and Shortest Paths, Worked (Dijkstra, Bellman-Ford, A*) used a heap: a tree kept so the smallest item always sits at the top, which is how Dijkstra’s search always knew the nearest unfinished town.

The idea in 30 seconds

Autocomplete has two jobs: find every stored word that starts with the typed letters, and return the few with the highest counts, the top-k.
A min-heap of size k keeps the weakest of the best-so-far on top, so each new candidate needs one comparison instead of a full sort.
Scanning a whole word list costs the same on every keystroke; 234,454 words took 11 to 14 ms per keystroke in Python on 2026-09-27.
In a trie, the words that start with a prefix are exactly the subtree below the prefix’s node, but a one-letter subtree still held about 14,000 words to read.
Storing each node’s top-k in advance makes a suggestion one short walk plus one read, paid for with a slower build, more memory, and updates along a word’s whole path when its count changes.

Read the story · Skip to the numbers