Priority Queues & Top-K Problems

The sift-up and sift-down machinery from the last chapter exists to serve one extremely common abstraction: a priority queue - a queue, in the sense of the earlier stacks-and-queues module, where instead of "first in, first out," the promise is always "highest priority out first." A min-heap or max-heap is the standard way to implement one.

The Queue built earlier in this tier promised FIFO order regardless of the values inside it. A priority queue drops that guarantee entirely and instead promises that whatever comes out next is always the current minimum (or maximum) priority value, no matter what order items were pushed in - exactly the min-heap or max-heap property from the last chapter, wrapped in push and pop operations instead of raw array-index juggling.

Hand-rolling sift-up and sift-down was worth doing once, to see exactly what happens underneath, but in real Python code the standard library's heapq module already does it - operating directly on a plain Python list treated as a min-heap, with no wrapper class required.

heapq only provides a min-heap directly. For a max-heap, the standard trick is negating values on the way in and out - pushing the negative of a value, and negating the result again on pop - since "smallest negative" is the same as "largest positive."

Finding the K smallest (or largest) elements in a collection is the single most common real-world use of a heap - top-K search results by relevance, K nearest neighbors, the K most expensive calls in a performance trace. The key insight is that fully sorting the whole collection is never necessary to answer a top-K question: keep a heap of size K, and for every new element, compare it against the heap's current worst kept element, swapping it in only if the new one is better. Python's heapq module even ships this pattern pre-built.

Under the hood, heapq.nlargest(k, items) is smarter than sorting everything and slicing off the front k entries - for large collections where k stays small, it maintains a heap of size k while scanning items once, giving roughly O(n log k) instead of a full O(n log n) sort, a meaningful difference when n is huge and k is small, such as "the top 10 results out of 10 million."