The idea: keep only the k best, and watch the weakest of them

You want the k largest items of a long stream: the 10 best search hits out of a million, the 100 busiest IP addresses in a log, ORDER BY score DESC LIMIT 5. Sorting everything works, but it costs O(n log n) time and keeps all n items in memory. The trick is to keep only k items, in a min-heap of k slots. Its root is the smallest of the best k so far: the bar to beat.

Seven scores have been read. The min-heap of 5 slots holds 29, 42, 88, 91 and 63 with 29 at the root, the bar to beat. A new score of 36 is bigger than 29, so 29 is evicted and 36 sifts down. A new score of 12 is not bigger than 29, so it is dropped after one compare
Every new score is compared with the root once: it either evicts the root or is dropped.

For each new score x:

  • While the heap has fewer than k items, x goes in: write it into the next free slot and sift it up.
  • Once the heap is full, compare x with the root (1 compare). If x ≤ root, x cannot be in the top k, because k kept scores are already at least as big. It is dropped.
  • If x > root, the root is the weakest of the top k, so it is evicted. x takes slot 0 and sifts down: at each level 1 compare finds the smaller child and 1 more compares it with x.

When the stream ends, the heap holds exactly the top k. On the page, the top 5 of the 16 random scores are 95, 91, 88, 81 and 74, found with 40 compares and 11 swaps (Demo: top 5 of 16).

Why a min-heap, not a max-heap

It sounds backwards: you want the largest items, yet you use a heap that puts the smallest on top. The question each new item asks is "are you better than the worst one I am keeping?", and a min-heap answers that in O(1) by looking at the root. It also removes that worst one in O(log k). A max-heap would put the best item on top, which is the one you never want to throw away. For the k smallest items, flip it: use a max-heap of size k.

Cost: O(n log k) time, O(k) memory

Each item costs 1 compare with the root, plus a sift-down of at most log₂ k levels if it gets in. So the whole stream costs O(n log k) time, and memory holds only k items. When k is small (10, 100) and n is huge, that is close to one pass over the data. How many items get in depends on the input order:

Bar chart of compares for the top 5 of 16 scores: 17 for descending input, 40 for random order, 53 for ascending input, against about 64 for a full sort
Descending input is the best case and ascending input the worst; all of them beat sorting the whole stream.
input orderevicteddroppedcomparesswaps
descending (Demo: descending input)011176
random (Demo: top 5 of 16)744011
ascending (Demo: ascending input)1105319

On ascending input every new score is the biggest so far, so every one evicts the root and sifts down: the worst case. On descending input the first k are already the answer, and every later score is dropped with one compare. On random input the bar keeps rising, so later items get in less and less often: the i-th item is in the top k so far with chance k / i, so only about k ln(n / k) items ever get in. A bigger k lowers the bar: with k = 7 the same stream needs 41 compares and the heap has 3 levels (Demo: k = 7).

Getting the answer in order

The heap is not sorted: only the root is in a known place. To print the top k from best to worst, pop the root k times. Each pop moves the last item to the root and sifts it down, O(log k) per pop, so O(k log k) in all. The pops come out smallest first, so the result is written from the right end. In Demo: top 3, then ORDER BY … LIMIT 3 the result is 95, 91, 88, and the whole query costs 24 compares.

Where it is used

  • SQL ORDER BY … LIMIT k: when no index gives the order, MariaDB and MySQL can run the filesort with a priority queue of k rows instead of sorting the whole table (r_used_priority_queue in ANALYZE FORMAT=JSON). See MariaDB EXPLAIN vs ANALYZE and Top-k LIMIT; PostgreSQL calls the same thing a top-N heapsort.
  • Search engines score every matching document and keep the best 10 in a heap of 10 (Lucene's TopScoreDocCollector).
  • Libraries and analytics: Python's heapq.nlargest(k, items), "top 100 URLs" in log processing, and the top-k step of streaming jobs.

If all n items are already in an array, Quickselect finds the k-th largest in O(n) average time, but it needs the whole array in memory and changes it. The heap needs neither, so it works on a stream. See also Priority Queues, Heap Sort (the same pops, done for all n) and d-ary Heaps.

What the page leaves out

The stream is only 16 distinct scores, so ties (an item equal to the root is simply dropped here) and rows carrying more than a score are not shown. The page leaves out top-k over several machines (each keeps its own top k, then the partial lists are merged), approximate top-k for unbounded streams (Count-Min Sketch with a heap, Space-Saving), and sliding windows, where old items must leave the heap too.