K-th Largest
Keep only the k best seen so far in a heap whose root is the worst of them. A newcomer that cannot beat the root cannot be in the top k, so it is dropped without a second look. One that can pushes the root out and takes its place. When the stream ends, the root is the answer.
Find the 3rd largest of 9 values with a min heap that never holds more than 3. Once it is full, its root is the 3rd largest seen so far.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.
The heap is full and its root is 1. Next value is 5. What happens?
Answer: Replaces the root and sinks. 5 beats the root, so the top 3 changes: 1 out, 5 in.
The heap is full and its root is 2. Next value is 6. What happens?
Answer: Replaces the root and sinks. 6 beats the root, so the top 3 changes: 2 out, 6 in.
The heap is full and its root is 3. Next value is 4. What happens?
Answer: Replaces the root and sinks. 4 beats the root, so the top 3 changes: 3 out, 4 in.
The heap is full and its root is 4. Next value is 9. What happens?
Answer: Replaces the root and sinks. 9 beats the root, so the top 3 changes: 4 out, 9 in.
The heap is full and its root is 5. Next value is 7. What happens?
Answer: Replaces the root and sinks. 7 beats the root, so the top 3 changes: 5 out, 7 in.
The heap is full and its root is 6. Next value is 8. What happens?
Answer: Replaces the root and sinks. 8 beats the root, so the top 3 changes: 6 out, 8 in.
How it runs, step by step
Find the 3rd largest of 9 values with a min heap that never holds more than 3. Once it is full, its root is the 3rd largest seen so far.
Finding the 3rd largest value using a min heap of size 3. The values are 3, 2, 1, 5, 6, 4, 9, 7, 8.
3 goes in: the heap holds 0 of 3, so everything is kept.
3 is added to the heap, which now holds 1 of 3.
2 goes in: the heap holds 1 of 3, so everything is kept and 2 climbs to its level.
2 is added to the heap, which now holds 2 of 3.
1 goes in: the heap holds 2 of 3, so everything is kept and 1 climbs to its level. The heap is full now, and its root 1 is the 3rd largest so far.
1 is added to the heap, which now holds 3 of 3. The root 1 is the 3rd largest so far.
5 is larger than the root 1, so 1 can no longer be in the top 3. 1 leaves, 5 takes the root and sinks to its level. The new root 2 is the 3rd largest so far.
5 replaces the root 1 and sinks. The root is now 2.
6 is larger than the root 2, so 2 can no longer be in the top 3. 2 leaves, 6 takes the root and sinks to its level. The new root 3 is the 3rd largest so far.
6 replaces the root 2 and sinks. The root is now 3.
4 is larger than the root 3, so 3 can no longer be in the top 3. 3 leaves, 4 takes the root and sinks to its level. The new root 4 is the 3rd largest so far.
4 replaces the root 3 and sinks. The root is now 4.
9 is larger than the root 4, so 4 can no longer be in the top 3. 4 leaves, 9 takes the root and sinks to its level. The new root 5 is the 3rd largest so far.
9 replaces the root 4 and sinks. The root is now 5.
7 is larger than the root 5, so 5 can no longer be in the top 3. 5 leaves, 7 takes the root and sinks to its level. The new root 6 is the 3rd largest so far.
7 replaces the root 5 and sinks. The root is now 6.
8 is larger than the root 6, so 6 can no longer be in the top 3. 6 leaves, 8 takes the root and sinks to its level. The new root 7 is the 3rd largest so far.
8 replaces the root 6 and sinks. The root is now 7.
The 3rd largest is 7, the root. 0 values bounced off the root and 6 replacements sank in, each O(log k), so O(n log k) with only k values in memory.
The 3rd largest value is 7. 0 values were dropped and 6 replaced the root.
Write it yourself
Define kthLargest(values, k) and return the kth largest value. It runs in your browser against this lesson's own 3 examples.
// A heap of size k holds the k largest seen so far; anything smaller than its smallest can be dropped on arrival.function kthLargest(values, k) { return 0;}
Remember
- k-th largest uses a min heap of size k, so the root is the smallest of the k largest.
- A newcomer that does not beat the root is dropped in O(1). That is where the savings come from.
- O(n log k) and only k values in memory, which is what makes it work on a stream.
Topics covered
Related
Where this is used
SearchLucene and Elasticsearch result pages
A query can match millions of documents while the page shows ten. Lucene collects hits into a min heap of size k, so once it is full each further document is compared against the current k-th best score and discarded on one comparison. That root score doubles as a skip threshold: the scorer can jump over whole blocks of postings whose best possible score cannot reach it.
DatabasesORDER BY ... LIMIT in PostgreSQL
A query ending in ORDER BY x DESC LIMIT 10 does not sort the full result. PostgreSQL keeps a bounded heap of ten rows, which EXPLAIN reports as "Sort Method: top-N heapsort". Memory then scales with k rather than with the row count, so the sort stays inside work_mem instead of spilling to disk.
Machine learningNearest-neighbour search in FAISS
Finding the ten closest vectors to a query embedding means scanning candidates and keeping the closest k. FAISS holds them in a max heap whose root is the worst distance currently accepted, so a candidate is rejected with a single comparison. In its HNSW index that root also ends the search: the graph traversal stops as soon as the nearest unvisited candidate is farther than the root, because nothing reachable from it can be closer.
Operationstopk() in Prometheus
topk(5, rate(http_requests_total[5m])) picks the five busiest series out of thousands, and it is re-evaluated at every step across a range rather than once. The engine keeps a heap of five per group, so each series costs one comparison against the fifth-best value instead of a full sort at every timestamp.
Why it works this way
Why a min heap when you are looking for the largest?
The heap holds the k largest so far, and the only member you ever need to touch is the weakest one, because that is the one a newcomer would replace. A min heap puts exactly that value at the root. A max heap would keep the biggest of the k on top, which is the element least in danger, and the weakest one would be somewhere in the leaves, so every comparison would start with an O(k) scan to find it.
Why not just sort and take index n - k?
Sorting costs O(n log n) and needs every value in memory at once, so it is ruled out the moment the input does not fit. Quickselect is the better in-memory answer: O(n) on average, and faster than the heap when you already hold the whole array and want the answer once. It pays for that by reordering the array in place and degrading to O(n^2) on bad pivots unless the pivot is chosen carefully. The heap is not the fastest option in general, it is the one that still works when the input never ends.
k-th largest is a position, not a distinct rank
On [5, 5, 4] with k = 2 this returns 5, because the second largest element is the second 5. If you expected 4 you were asking for the second largest distinct value, which is a different question: deduplicate first, or the answer is off by however many duplicates sit above it. Problem statements are often vague here, so settle it before writing code.
The answer is only valid at the end, and the top k comes out backwards
peek() is the k-th largest only once every value has been offered. Mid-stream it is the k-th largest of what has arrived so far, which is a different number. It is meaningless if fewer than k values ever arrive, since the root is then just the minimum, so guard for n >= k. The heap does hold the whole top k for free, but draining it yields ascending order, so a ranked list has to be reversed.
Read more
- Selection algorithmWikipedia
- QuickselectWikipedia
- heapq: nlargest and nsmallestPython docs · docs.python.org
- PriorityQueueOracle Java 21 · docs.oracle.com
- nth_elementcppreference