Heaps and Priority Queues
A heap answers one question fast: which item is the smallest? It absorbs inserts and removals in O(log n) while it keeps answering, and it does so as a binary tree stored in a plain array with no pointers at all. Its order is loose enough to be cheap and strict enough to put the minimum first.
That is exactly what a timer list, a job scheduler, a shortest-path search and Lantern's first page of results need. None of them wants everything sorted. Each wants the next item, over and over, while new items keep arriving.
The Heap Property
In a min-heap every parent is no larger than its children, so the root is the minimum. Nothing else is promised. Two siblings are in no particular order, no level is sorted, and the largest item can sit on any leaf. A max-heap is the same with the comparison reversed.
That looseness is the point. A search tree has to keep every key in its exact place relative to every other key, and pays for it with rotations. A heap only has to keep each parent above its own children, a rule that one swap at a time can restore.
A Tree Stored in an Array
A heap is kept complete: every level is full except possibly the last, which fills from the left. A complete tree has no gaps, so it maps onto an array level by level. The root is slot 0. The children of slot i sit at slots 2i + 1 and 2i + 2, and its parent sits at slot i minus one, divided by two and rounded down.
The arithmetic replaces the pointers. There is no per-node allocation and no pointer to chase, and the whole heap is one contiguous block of memory, which Chapter 4 showed is what the cache rewards. Python's standard heapq module works this way, on an ordinary list.
Push, Pop and Build
A push appends the new item at the end of the array and swaps it upward while it is smaller than its parent. A pop takes the root, moves the last item into its place and swaps that item downward with the smaller of its children until neither child is smaller. Each operation makes at most one swap per level, about 20 for a million items, and peeking at the minimum without removing it is O(1). Measured on Python 3.15, ten pops from a heap of a million items made 195 comparisons, about 20 each.
Building a heap from n unsorted items in one pass, sinking each parent from the bottom level up, is O(n), cheaper than n separate pushes. Most nodes sit near the bottom and have little distance to sink: half the nodes are leaves and never move. Measured on the worst order for a min-heap, a million keys in descending order, the one-pass build made 1.5 million comparisons, while a million pushes of the same keys made 18 million.
Lantern's Ten Best
A query can match 400,000 records, and the first page shows only the 10 with the highest scores. Sorting all 400,000 by score to keep ten costs about n log n comparisons, some 7.4 million by the formula, and holds every match in memory; CPython's sort of 400,000 random scores measured 6.9 million.
Lantern keeps a min-heap of 10 instead. Its root is the weakest of the ten best seen so far, the one a newcomer has to beat. Each candidate is compared with the root. If it is not higher, it is discarded after that single comparison. If it is higher, it replaces the root and sinks to its place in at most three swaps. Measured on 400,000 random scores, the pass made one comparison per candidate and replaced the root only 96 times. The whole pass is O(n log k) for the k best, memory stays at 10 entries instead of 400,000, and the full sort never happens.
Timers, Schedulers and Shortest Paths
Anything that asks "what is due next" is a heap. Python's asyncio keeps its scheduled callbacks in a heap ordered by due time, and Chapter 11 shows the event loop that pops them. Dijkstra's shortest-path algorithm takes the nearest unvisited node from a heap, which Chapter 8 walks through. Job schedulers order work by priority or deadline, and an external sort merges its sorted runs through a heap that holds the head of each run, the subject of Chapter 7.
The heap is not the only answer. Operating system kernels often keep their timers in timer wheels, arrays of buckets indexed by expiry time, which trade some precision for O(1) inserts; the Linux kernel is one of them. But when a program needs "the smallest next" with inserts in between, the heap is the default.
What a Heap Cannot Do
A heap is fast at one question and poor at all the others. It cannot find an arbitrary item, since the item could be anywhere below its parent, so a search is O(n). It cannot cheaply remove an item from the middle. It does not iterate in order: walking the array yields heap order, not ascending order.
A job queue that must cancel or reprioritize pays O(n) per change if it searches for the job. The standard trick is lazy deletion: mark the entry cancelled, leave it in place, and skip it when it surfaces at the root. That is what asyncio does with cancelled timers. It counts them, and once more than half of a heap of over 100 entries are dead, it rebuilds the heap without them. The price is memory held by dead entries until they are popped or the rebuild happens.
A heap, this topic, is a data structure: an array ordered so that its smallest item comes first. Use it for priority queues, top-k and "what is due next".
The heap of Chapter 4 is the region of memory where objects of any size and lifetime are allocated. The two share a name by accident of history and nothing else; a heap data structure is usually one array that itself lives on the memory heap.
- "A heap keeps its items sorted." Only the root is guaranteed. The underlying array is not sorted, and iterating over it yields heap order, not ascending order.
- "To get the top ten, sort and slice." A sort costs n log n comparisons and holds every item. A ten-item heap streams the input in one pass with memory for ten.
- "The largest k items need a max-heap." A min-heap of size k is the right shape, because its root is the weakest survivor and the only item a newcomer has to beat.
- "Equal priorities come out in the order they went in." A heap is not stable; equal priorities leave in arbitrary order. In Python a tie falls through to comparing the payloads, and when those are dictionaries the push raises TypeError: the less-than operator is not supported between two dicts.
- "Cancelling a job in a priority queue is cheap." Finding it is O(n). Mark it cancelled and skip it when it reaches the root instead.
- Keep a size-k min-heap for any top-k over a stream. Memory stays at k, and most items cost one comparison.
- Add an insertion counter as a tie-breaker to every heap entry. Equal priorities then leave in arrival order, and the payloads are never compared.
- Cancel by marking and skipping, and rebuild the heap when dead entries pile up. Cancellation becomes O(1) for a bounded memory cost.
- Use a heap for a repeated "smallest next" with inserts in between, and sort once when you need everything in order. A heap drained item by item is a slower sort.
Knowledge Check
A query matches 400,000 records and the page shows the best 10. What does a 10-entry min-heap cost compared with sorting everything?
- About the same, since both end up comparing every pair of scores
- About one comparison per match, against millions for the full sort
- More work, because every candidate must sink through the heap
- Less memory but more comparisons, because a heap re-sorts itself
A developer prints the array behind a min-heap and finds it is not in ascending order. What does that mean?
- The heap is corrupted and must be rebuilt before it is used again
- Nothing is wrong: the heap only keeps each parent below its children
- The heap was built with pushes instead of one heapify pass
- A max-heap was built by mistake, so the array is in descending order
To keep the 10 largest scores from a stream, which structure is the right shape?
- A min-heap of 10, whose root is always the weakest of the ten kept
- A max-heap of 10, whose root is the strongest of the ten kept
- A max-heap of the whole stream, popped ten times at the very end
- A sorted list of 10, with each newcomer inserted by a linear scan
A job queue built on a heap must support cancelling jobs. What is the usual approach?
- Search the array for the job and swap it with the last entry
- Rebuild the whole heap from the remaining jobs after each cancel
- Mark the job cancelled, and skip it when it reaches the root
- Move the job to the root by lowering its priority, then pop it
A Python program pushes tuples of priority and a dict onto a heap, and two jobs share a priority. What happens?
- The two jobs come out in the order they were pushed
- The second job silently replaces the first one in the heap
- The heap sorts the two jobs by the size of their dictionaries
- The tie falls through to comparing the dicts, which raises TypeError
You got correct