Free Python developer course
Go from your first line of code to working as a Python developer: projects, testing, data, databases, web apps and APIs, all in your browser.
A list read as a tree: the best k of a million without sorting, and where top-k hides in AI work.
Sorting a million scores to read the best ten is a lot of work for ten answers. A heap keeps just enough order to hand you the best item at any moment, and to find the next best after you take it. It is the structure behind a priority queue, and behind a surprising amount of AI engineering: picking the top-k tokens when sampling, the top-k documents in retrieval, the open list in beam search and the frontier in nearest-neighbor search over a graph. The idea is small: a list, read as a tree.
Keep a small structure of the best 10 seen so far and update it as you scan
A scan that keeps the best 10 so far looks at each score once and only does extra work for the few that beat the current tenth. Sorting everything orders a million items to answer a question about ten. That is the idea of a heap.
This rests on Core data structures: a list holds items in order, and a stack or a queue decides which one comes out next. A priority queue decides by importance: whatever comes out is always the smallest (or the largest) item inside.
A heap is the usual way to build one. It is an ordinary list, read as a tree. Draw item 0 at the top. Its children are items 1 and 2. The children of item 1 are items 3 and 4, and so on. For any index i:
2i + 1 and 2i + 2;(i - 1) // 2.A min-heap keeps one rule: every parent is less than or equal to its children. So the smallest item is always at index 0, and checking that costs nothing. Nothing else is ordered: two siblings may be in either order, and cousins have no relation at all. That is the whole saving. A heap keeps just enough order to find the minimum, and so is much cheaper to maintain than a fully sorted list.
3
A stack is last in, first out, so the 3 comes back first. A priority queue changes the rule: what comes back is not the last in or the first in, but the smallest.
Push and pop keep the rule. To push, put the new item at the end of the list, the next free spot in the tree, and let it sift up: while it is smaller than its parent, swap them. To pop the minimum, take the item at index 0, move the last item of the list into its place, and let it sift down: while it is larger than its smaller child, swap with that child.
Each swap moves one level, and a tree of n items has about log₂ n levels. So push and pop each take about log₂ n steps, whether the heap holds ten items or a million.
The picture. Watch a new 1 enter the heap [2, 5, 3, 9, 6]. It lands at the end, and climbs while it is smaller than its parent.
The new item climbs two levels. Every other pair of parent and child was already in order, so nothing else moves.
Write a sentence or two, then compare it with a good answer in the lesson.
Purpose. Build the two operations from the picture, then meet the library version that real code uses.
Here is the heap as a class: a list, push with sift up and pop with sift down.
class MinHeap: def __init__(self): self.items = [] def push(self, x): items = self.items items.append(x) i = len(items) - 1 while i > 0 and items[i] < items[(i - 1) // 2]: parent = (i - 1) // 2 items[i], items[parent] = items[parent], items[i] i = parent def pop(self): items = self.items top = items[0] last = items.pop() if items: items[0] = last i = 0 while 2 * i + 1 < len(items): child = 2 * i + 1 if child + 1 < len(items) and items[child + 1] < items[child]: child += 1 if items[i] <= items[child]: break items[i], items[child] = items[child], items[i] i = child return top heap = MinHeap() for x in [5, 2, 9, 1, 7]: heap.push(x) print(heap.items) print([heap.pop() for _ in range(5)])
Pushing five numbers leaves the heap in a mixed order, but popping them returns every number in order, smallest first. That is heap sort: push everything, then pop everything.
Code flow. The pop, line by line. The last item jumps to the top, then sinks, always swapping with its smaller child so the rule holds on both sides.
import heapq heap = [] for x in [8, 3, 5, 1, 9]: heapq.heappush(heap, x) print(heapq.heappop(heap), heapq.heappop(heap), heap[0])
1 3 5
heappop always returns the smallest left: first 1, then 3. After those two, the smallest of 5, 8 and 9 is 5, which sits at index 0.
import heapq scores = [0.4, 0.9, 0.1, 0.7] print(heapq.nlargest(2, scores), heapq.nsmallest(1, scores))
[0.9, 0.7] [0.1]
nlargest(2) returns the two biggest, biggest first: 0.9 and 0.7. nsmallest(1) returns the single smallest, 0.1.
[2, 4, 9]
The last item, 9, moves to the top: [9, 4, 2]. Its smaller child is 2, so they swap: [2, 4, 9]. Now 9 is at index 2 and has no children, so it stops.
Write is_min_heap(items): True when every item is at least as large as its parent, using the parent index (i - 1) // 2. An empty list and a one-item list are heaps.
def is_min_heap(items): ... print(is_min_heap([1, 5, 2, 9]), is_min_heap([5, 1, 2]))
Write top_k(items, k): the k largest items, largest first, scanning the items once and keeping a min-heap of at most k items with heapq. For each item, push it. If the heap grows past k, pop the smallest. The heap never holds more than k.
import heapq def top_k(items, k): ... print(top_k([5, 1, 9, 3, 7, 8], 3))
Plot it. Ten best of n numbers, by sorting everything and by keeping a heap of ten. Both lines must read every number, so both rise with n. The sort also has to order all of them, which costs more.
from academy import measure import heapq import random def make(n): rng = random.Random(1) return [rng.random() for _ in range(n)] measure( {"sort all, take 10": lambda d: sorted(d)[-10:], "heap of 10": lambda d: heapq.nlargest(10, d)}, [10_000, 20_000, 40_000, 80_000, 160_000], setup=make, repeat=2, xlabel="numbers", )
Do not read exact times off the chart: they change from machine to machine. Look at the shapes. Both lines slope up, and the heap's line sits below the sort's, because it never orders the other 160,000 numbers.
About twice, a slope of about 1
The scan looks at every item once, so doubling the items doubles the reading. Only the few items that beat the current tenth cause extra work. That is a slope of about 1 on log axes.
A priority queue serves the most urgent job first. heapq compares tuples item by item, so a job is a pair, (priority, name), with the smallest priority number first.
import heapq jobs = [(3, "send digest"), (1, "charge card"), (2, "resize image"), (1, "email receipt")] queue = [] for job in jobs: heapq.heappush(queue, job) order = [] while queue: order.append(heapq.heappop(queue)[1]) print(order)
The two priority-1 jobs come out first, in name order, because tuples that tie on the first item are compared on the second: "charge card" before "email receipt". Then priority 2, then priority 3. For jobs that cannot be compared as tuples, add a counter as the second item, (priority, count, job), so a tie never has to compare the jobs themselves.
Write a sentence or two, then compare it with a good answer in the lesson.
Purpose. The same structure answers four questions an AI engineer asks every week.
The model gives a score to every token in its vocabulary, often over 100,000 of them. Top-k sampling keeps the k best and chooses among them. The cell does that with PyTorch's topk, and then with heapq over the same scores. A retrieval system does the same with document scores, keeping the best few:
import heapq import torch logits = torch.tensor([2.0, 1.0, 0.1, 3.0, -1.0, 2.5]) values, ids = torch.topk(logits, 3) print(values.tolist(), ids.tolist()) pairs = heapq.nlargest(3, enumerate(logits.tolist()), key=lambda p: p[1]) print([i for i, _ in pairs] == ids.tolist()) docs = {"doc a": 0.62, "doc b": 0.91, "doc c": 0.35, "doc d": 0.88, "doc e": 0.47} print(heapq.nlargest(2, docs.items(), key=lambda kv: kv[1]))
(This page runs a teaching subset of PyTorch: same calls, CPU only.) The two methods agree on the three best tokens. In a real model torch.topk runs on the whole tensor at once, on the GPU, but the question is the one you just answered.
Two more heaps hide in AI work. Beam search keeps a list of the best partial sentences so far and always extends the most promising one: that is a priority queue ordered by score. Nearest-neighbor search in a vector index walks a graph and keeps the candidates it has not yet visited in a priority queue, nearest first. In both, "give me the best one now, and let me add more" is exactly what a heap does cheaply.
On the job: when you see
sorted(x)[:k]on a big list, ask whetherheapq.nsmallest(k, x)ortorch.topkwould do. And when you add a priority to jobs, tasks or search candidates, use a heap, not a list you re-sort after every insert.
Write a sentence or two, then compare it with a good answer in the lesson.
In a heap stored in a list, which index holds the parent of the item at index 10?
575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.
Go from your first line of code to working as a Python developer: projects, testing, data, databases, web apps and APIs, all in your browser.
Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write