Index Ai Academy
Phase 7 · Data structures & algorithms

Heaps and priority queues

A list read as a tree: the best k of a million without sorting, and where top-k hides in AI work.

About 35 minutes · A free account opens the whole lesson.
Already have an account? Sign in to open this lesson

What it covers6

Why it matters

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.

What you'll be able to do

  • Draw a list as a binary tree, and find any item's parent and children from its index
  • Trace a push (sift up) and a pop (sift down) by hand, and say why each takes about log n steps
  • Build push and pop from scratch, then use heapq, and take the top k of a large list without sorting it
  • Recognize where heaps hide in AI work: sampling, retrieval, beam search and nearest-neighbor search
Quick check
A guess before we start. You have a million scores and want the best 10. Which approach does the least work?
  1. Compare every pair of scores
  2. Keep a small structure of the best 10 seen so far and update it as you scan
  3. Sort all million of them first, then take the last ten from the end
  4. Print them all and look
Show the answer

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.

The idea: a list, read as a tree

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:

  • the children are at 2i + 1 and 2i + 2;
  • the parent is at (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.

Quick check
From the lesson on core data structures: a stack gives back the last item put in. You push 1, 2 and 3, then pop once. What do you get?
  1. [1, 2]
  2. 1
  3. 3
  4. 2
Show the answer

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.

Try it now

The new item climbs two levels. Every other pair of parent and child was already in order, so nothing else moves.

In your own words
In your own words: why does a heap find the smallest item at once, while a sorted list costs far more to keep up to date?

Write a sentence or two, then compare it with a good answer in the lesson.

In Python: push and pop from scratch, then heapq

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)])
It runs right here in your browser, with nothing to install.

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.

Quick check
What does this print?
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. 1 3 8
  2. 8 3 5
  3. 1 3 5
  4. 9 8 5
Show the answer

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.

Quick check
What does this print?
import heapq

scores = [0.4, 0.9, 0.1, 0.7]
print(heapq.nlargest(2, scores), heapq.nsmallest(1, scores))
  1. [0.9, 0.7] [0.1]
  2. [0.9, 0.7] [0.9]
  3. [0.4, 0.9] [0.1]
  4. [0.1, 0.4] [0.9]
Show the answer

[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.

Quick check
A min-heap holds [1, 4, 2, 9]. Which list is the heap after popping the 1?
  1. [4, 2, 9]
  2. [2, 9, 4]
  3. [9, 4, 2]
  4. [2, 4, 9]
Show the answer

[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.

Drill

Is this list a heap?

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]))
In the lesson, your code is checked as you write it.
Drill

The k largest, keeping only k

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))
In the lesson, your code is checked as you write it.

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.

Quick check
On the chart, the number of items doubles from 80,000 to 160,000. About how does the work for the heap line grow?
  1. It stays about the same
  2. About twice, a slope of about 1
  3. About four times as long
  4. About eight times as long
Show the answer

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.

Worked example

Worked example: a task queue by priority

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)
In the lesson you can change this and run it.

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.

In your own words
Why does keeping a heap of the best k scale better than sorting everything when you only need the top 10 of a million?

Write a sentence or two, then compare it with a good answer in the lesson.

In AI and ML engineering: top-k everywhere

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 whether heapq.nsmallest(k, x) or torch.topk would 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.

In your own words
A retrieval service scores 2 million documents for each query and needs the best 10. What would you do, and why not just sort?

Write a sentence or two, then compare it with a good answer in the lesson.

Goes deeper in

Practice what you just read

  • 4 code examples you can edit and run
  • a practice exercise that checks your code
  • a 5-question quiz
  • 9 review cards for spaced repetition

Try a quiz question

In a heap stored in a list, which index holds the parent of the item at index 10?

  1. 4
  2. 5
  3. 9
  4. 3

Answer it at the end of the lesson to see if you're right, and why.

Before this lesson

Keep learning

Where this lesson leads.

575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.

Phase 7 · about 48 hours of study

Software engineering

How software is built, from bits to tested, well-designed programs 59 lessons 1 free
  1. Iterators and generators FreeThe iteration protocol, yield, lazy pipelines and itertools, in small memory.45 min
  2. Context managersSetup and cleanup that always run: with, contextlib, transactions and atomic writes.35 min
  3. Closures and decoratorsFunctions that remember, wrap and extend other functions.40 min
  4. Exceptions in depthError hierarchies, chaining, notes, exception groups and warnings.40 min
  5. Pattern matchingmatch and case: literal, sequence, mapping and class patterns with guards.35 min
  6. Text, bytes and encodingsstr and bytes, UTF-8, decoding errors, normalization and base64.35 min
  7. Binary filesBytes as numbers, endianness, struct records, file signatures and checking uploads.45 min
  8. Testing your codeAutomated tests that prove code works and keep it working.45 min
  9. Testing with pytestFixtures, parametrize, mocks, temporary files and coverage.45 min
  10. Testing numeric and random codeClose enough for floats, seeds and what they fix, properties that hold for any input, a gradient check and overfit-one-batch.40 min
  11. Debugging systematicallyFind any bug with a method instead of guesswork.35 min
  12. Readable code and refactoringWrite code people can understand, and improve it safely.35 min
  13. Code style and toolsPEP 8, formatters, linters and type checkers, and how they fit together.35 min
  14. Types and data modelingType hints, dataclasses and checking data at the edges of a program.35 min
  15. Typing in depthGenerics, protocols, TypedDict, Literal and narrowing, checked by mypy.45 min
  16. Classes in depthProperties, alternative constructors, abstract base classes and tuned dataclasses.40 min
  17. Make your classes feel built inSpecial methods for printing, equality, ordering, arithmetic and containers.45 min
  18. Software designModules, interfaces and dependencies that keep big programs changeable.45 min
  19. LoggingLoggers, levels, handlers and configuration, without leaking secrets.40 min
  20. How computers run codeBits, memory, the processor, and what really happens when Python runs.40 min
  21. Arrays in memoryBuffers, dtypes, shapes and strides: why a transpose is free, and which operations copy.40 min
  22. Algorithm complexityCount the work code does, and see why some programs stop scaling.40 min
  23. Concurrency and asyncDo many things at once: processes, threads and the event loop.45 min
  24. Performance and profilingMeasure before you optimize, then fix the part that matters.45 min
  25. Profiling numeric code and a training loopWhere a training step spends its time, Amdahl's rule by hand, and cProfile on a loop with a slow batch function.40 min
  26. Reading C, C++, CUDA and RustPointers and loops in C, references and templates in C++, one-thread-per-element CUDA kernels, and Rust's Option, Result and ownership.30 min
  27. Core data structuresArrays, linked lists, stacks, queues and the hash table behind every dict.45 min
  28. Heaps and priority queuesA list read as a tree: the best k of a million without sorting, and where top-k hides in AI work.35 min
  29. Recursion, trees and graphsFunctions that call themselves, and the shapes most real data takes.45 min
  30. Searching, sorting and dynamic programmingThe classic algorithms, and the ideas behind them.45 min
  31. Dynamic programming in depthA method in five questions: state, choices, recurrence, base case and order. Coins where greedy fails, rebuilding the solution, packing a token budget, the likeliest path behind noisy readings, and what it costs.45 min
  32. Binary search trees and traversalsInsert, search and delete in a sorted tree, walk it four ways, and see why balance and B-trees matter.45 min
  33. Patterns for coding problemsTwo pointers, counting with dictionaries, prefix sums and sliding windows: O(n) answers to classic problems.45 min
  34. Project: a spell checker, three waysA sorted list, a hash set and a trie, measured for speed and memory, with suggestions.45 min
  35. Searching for solutionsBacktracking with pruning, Dijkstra's algorithm and A*, ending with an optimal sliding-puzzle solver.45 min
  36. Project: an unbeatable game opponentGame state and rules, minimax with a cache, and an exhaustive test that proves it never loses.45 min
  37. Databases and SQLStore, query and join data with the language every database speaks.40 min
  38. SQL for analysisSubqueries, CASE, common table expressions, outer joins and window functions on real order data.45 min
  39. Designing a databaseFrom one big table to related tables: keys, constraints, many-to-many and a loader that is safe to rerun.40 min
  40. Databases with an ORMSQLAlchemy models, sessions, relationships, transactions and the N+1 problem.45 min
  41. Changing a database safelyNumbered migrations in transactions, required columns and backfills, and expand-and-contract changes.40 min
  42. Secure codingInjection, escaping, secrets and passwords: the mistakes attackers look for.40 min
  43. Projects, packaging and CILay out a real project, pin its dependencies and test it on every push.35 min
  44. Config files: YAML and TOMLWrite YAML and TOML that parse as you meant, dodge the type traps, and validate what you load.25 min
  45. Command-line programsargparse subcommands, stdin, exit codes and testable main functions.40 min
  46. Packaging your codepyproject.toml, the src layout, versions, entry points and wheels.45 min
  47. Pipes and text tools in the shellgrep, wc, sort, uniq, head and cut, chained with pipes to answer questions about logs and data.25 min
  48. JSON on the command line: curl and jqCall APIs with curl, fail on HTTP errors, and pull values out of JSON with jq paths and select.25 min
  49. Shell scripts that fail safelyTurn commands into scripts with variables, set -euo pipefail and clear exit codes, and know when to switch to Python.25 min
  50. Reading and writing XMLElementTree, attributes and text, namespaces, building XML safely, and untrusted input.35 min
  51. Project: a word-guessing gamePlan a game with a flowchart, then build it from tested functions and one input loop.40 min
  52. Project: a card game of 21Turn written rules into functions, and make randomness testable.40 min
  53. Project: a drinks kioskA program with state and commands, built with functions, then refactored into classes.45 min
  54. Project: a flashcard trainerCards from a file, review boxes, and progress saved between runs.45 min
  55. Project: a price-watch alert botAn API client, alert rules, digest emails and a state file, so reruns never repeat.45 min
  56. Project: Pack Train, an arcade gameA grid game on the turtle canvas: game state as classes, a timer loop, key handlers and a saved best score.45 min
  57. Project: a private password-breach checkHash locally, send five characters, match locally: k-anonymity, safe logging and failure handling.40 min
  58. Capstone: a command-line appDesign, build and test a complete program with a database.45 min
  59. Capstone: ship a small model libraryA typed, tested and profiled package with a train and an eval command, a YAML config, logging and a wheel.45 min
Part of a free course 127 lessons

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.

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