cf.completefrontend
HEAPS & PRIORITY QUEUES · CORE

Top K elements with a heap

Find the k largest items by keeping a small min-heap of size k and throwing out its smallest item whenever it grows too big.

Time O(n log k)Space O(k)10 practice problemsStep-through picture

The idea

Often you only need the best few items: the 10 slowest page loads, the 5 most used tags, the 3 closest stores. Sorting everything costs O(n log n), and it needs the whole list in memory at once.

Instead, keep a min-heap that never holds more than k items. Add each new item. If the heap now has k + 1 items, pop the smallest one. The items left are always the k largest seen so far, and the heap's top is the smallest of them: the k-th largest.

It feels backwards to use a min-heap to find the largest items, but it is the right tool: the item you need to throw out is the weakest of your current top k, and a min-heap keeps exactly that item at the top.

An everyday example

A talent show with only k chairs on stage

A talent show has 3 chairs on stage for the best acts so far. Each new act walks onto the stage. If there are now 4 acts, the weakest of the four leaves. You never compare the newcomer with everyone who has already left; you only need to know who the weakest on stage is. When the show ends, the three acts on stage are the top three.

How the example maps to the code
In the exampleIn the code
The chairs on stagethe heap, kept at k items
A new act walks onheap.push(num)
Too many acts on stageheap.size > k
The weakest act leavesheap.pop()
The weakest act still on stage at the endthe heap's top: the k-th largest

From the slow way to top k elements with a heap

  1. The obvious way to get the k largest of n numbers is to sort them all and take k from the big end. That costs O(n log n) time and needs every number in memory at once. It also does far more work than asked: it puts thousands of losers in perfect order when only the winners matter.
  2. Think about what you would keep while reading the numbers one by one. You only need the best k seen so far. When a new number arrives, the only question is whether it beats the weakest of your current k. If it does, the weakest drops out and the new one joins. If not, the new one is ignored.
  3. So you need a group of about k items where the weakest is always ready to look at and remove, while new items keep joining. That is exactly a min-heap: its top is the smallest item, and push and pop cost O(log k), because the heap never holds more than k + 1 items.
  4. The code does this in the simplest way: push every number, and if the heap now has k + 1 items, pop the smallest. A number too small to join is pushed and popped right away. After the last number, the heap holds the k largest, with the k-th largest on top. Push, trim back to k, repeat: that loop is the top K pattern.

How it works

  1. Make a min-heap with new MinHeap((a, b) => a - b).
  2. For each num, push it into the heap.
  3. If the heap has more than k items, pop the smallest. It can't be in the top k.
  4. After the loop, the heap holds the k largest values, smallest on top.
  5. To return them from largest to smallest, pop them all into result and reverse it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function topK(nums, k) {
  2. const heap = new MinHeap((a, b) => a - b);
  3. for (const num of nums) {
  4. heap.push(num);
  5. if (heap.size > k) heap.pop();
  6. }
  7. const result = [];
  8. while (heap.size > 0) result.push(heap.pop());
  9. return result.reverse();
  10. }

How fast it is

TimeO(n log k)
Extra memoryO(k)

Each of the n items is pushed and maybe popped on a heap that never holds more than k + 1 items, so each operation costs O(log k).

  • Best caseO(n)

    k is a small fixed number like 1 or 3: each push and pop touches only a couple of levels, so the run is one pass over the input.

  • Average caseO(n log k)

    Each of the n numbers costs one push and usually one pop on a heap of at most k + 1 items.

  • Worst caseO(n log k)

    Every push and pop travels the heap's full height, about log₂ k levels. When k is close to n, this approaches O(n log n), the same as sorting.

Common mistakes

  • Using a max-heap of all n items and popping k times. It works, but costs O(n) memory and loses the streaming benefit.
  • Using a max-heap with size k for the k largest. The top of a max-heap is the biggest item, which is the one you want to keep, not throw out. Use a min-heap for the k largest and a max-heap for the k smallest.
  • Forgetting a tie-break when scores can be equal. Two runs may pick different items. Order ties by a second key.
  • Returning the heap's array directly. It is in heap order, not sorted order. Pop the items, or sort the final k.

When to use it

Look for these clues in a problem:

  • The question asks for the k largest, k smallest, k most frequent, or k closest items.
  • It asks for the k-th largest or k-th smallest value.
  • The data arrives as a stream and you can't keep or sort all of it.
  • k is much smaller than n, so O(n log k) beats sorting.

Check yourself

Answer each one in your head first, then open it.

Why use a min-heap to find the largest items?

The item you remove each time is the weakest of your current top k, which is the smallest. A min-heap keeps exactly that item on top.

In the trace, why does pushing 3 leave the group unchanged?

3 is smaller than all three members, so after the push it is the smallest of four and is the one popped.

How much memory does it use for a stream of a million numbers with k = 10?

A heap of at most 11 numbers. The stream itself is never stored.

What is on top of the heap after the loop?

The k-th largest number, the smallest member of the top k. In the trace that is 8.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: after each number is handled, the heap holds the largest k numbers seen so far, or all of them if fewer than k have been read. Before the first number the heap is empty, which is correct.

Each step keeps it. The new num is pushed, so the heap holds the old top k plus num. If that makes k + 1 items, the new top k is those items minus the smallest one, and the pop removes exactly that smallest one. If num is the smallest, it is the one removed, and nothing changes.

A dropped number can never be needed later. When it was popped, it was the smallest of k + 1 numbers, so at least k numbers were at least as big. Later steps only swap members for bigger ones, so those k stay at least as big, and the dropped number can't climb back into the top k.

After the last number, the rule says the heap holds the k largest of the whole input. Popping a min-heap gives them from smallest to largest, so reversing the list gives them largest first.

Going deeper

3 more ideas

Why the heap always holds the top k so far

Assume the heap holds the k largest values among the items seen so far. A new item arrives. If it belongs in the top k, the item that drops out is the smallest of those k + 1, which is exactly what pop removes. If it doesn't belong, it is itself the smallest and gets popped right away. Either way the rule still holds.

Ranking by something else

Change the compare function to rank by any score. For the k most frequent words, count each word with a Map, then push [word, count] pairs into a min-heap ordered by count. For the k closest points, push points into a max-heap ordered by distance and pop the farthest when the heap is too big. Add a tie-break (such as the word in alphabetical order) so the answer is unique.

Time and memory compared with sorting

Each item costs one push and maybe one pop on a heap of at most k + 1 items, so the time is O(n log k) and the memory is O(k). Sorting is O(n log n) with O(n) memory. For a million items and k = 10, log k is about 3, while log n is about 20.

Work it by hand

Every step in a table, with why

Find the 3 largest of 7 numbers. The heap is shown as its array, which is in heap order, not sorted order.

nums = [6, 2, 11, 5, 9, 3, 8], k = 3

StepnumAfter pushPoppedheap afterWhat happensWhy
16[6]-[6]1 item: keep itThe heap has room, so nothing is removed.
22[2, 6]-[2, 6]2 items: keep both2 is smaller than 6, so it climbs to the top.
311[2, 6, 11]-[2, 6, 11]3 items: the heap is fullNow there are exactly k items. From here on, every push makes 4 items and forces one pop.
45[2, 5, 11, 6]2[5, 6, 11]4 > 3: drop the smallest2 is the weakest of the four, so it leaves. The top 3 so far are 5, 6, and 11.
59[5, 6, 11, 9]5[6, 9, 11]5 drops out9 beats the weakest member, 5, so 5 leaves.
63[3, 6, 11, 9]3[6, 9, 11]3 itself drops out3 is smaller than all three members. It rises to the top and is popped right away, so the group doesn't change.
78[6, 8, 11, 9]6[8, 9, 11]6 drops out8 beats 6. The heap now holds the final top 3, with the third largest, 8, on top.

Popping the heap gives 8, 9, 11, and reversing gives [11, 9, 8]. The heap never held more than 4 numbers, however long the input was.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Top K elements with a heapO(n log k)O(k)k is much smaller than n, or the numbers arrive as a stream that you can't keep.
Sort everythingO(n log n)O(n)The input is small, or you need it sorted anyway. It is one line: [...nums].sort((a, b) => b - a).slice(0, k).
QuickselectO(n)O(1)The whole array is in memory, you may reorder it, and you want the best average time. Its worst case is O(n²), and it can't work on a stream.
Counting bucketsO(n)O(n)The scores are small whole numbers, like counts from 1 to n. Put each item in a bucket by score and read the buckets from the top.

Extra memory: O(k) for the heap, plus O(k) for the result. The input can be a stream that is never stored.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Top K elements with a heap and the other approaches, on a scale where each line up is 10 times more steps.
  • Top K elements with a heap, Sort everything O(n log k)
  • Quickselect, Counting buckets O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Top K elements with a heap339,96620 million
Sort everything339,96620 million
Quickselect101,0001 million
Counting buckets101,0001 million

Inputs that need care

6 tricky inputs
k is 0: topK([4, 1, 9], 0)
After every push the size is 1 > 0, so every number is popped, and it returns []. That is correct, but an early return is clearer.
k bigger than the input: topK([4, 1], 5)
The heap never reaches k + 1 items, so nothing is popped, and it returns every number, largest first: [4, 1].
Duplicates: topK([7, 7, 7, 2], 2)
It returns [7, 7], because equal values are separate entries. For the top k different values, skip numbers you have already kept, using a Set.
Negative numbers: topK([-3, -9, -1], 2)
Nothing changes: (a, b) => a - b works for any numbers, and it returns [-1, -3].
Ties when ranking objects by a score
Which tied object stays depends on the push order. Add a second key to the compare, such as the name, so the same input always gives the same answer.
The k smallest instead of the k largest
Use a max-heap, (a, b) => b - a, and pop when the size goes over k. The rule to remember: the heap's top is always the item you would throw out next.

Variations and follow-ups

Twists interviewers add

Only the k-th largest

Return heap.peek() after the loop instead of popping everything. In a stream, that value is ready after every new number, so a dashboard can show the current k-th largest at any moment in O(1).

Skip numbers that can't join

Once the heap holds k items, compare num with heap.peek() first and skip it if it isn't bigger. Small numbers then cost one comparison instead of a push and a pop, and the answer is the same.

Top k by frequency

Count each item with a Map in one pass, then run the same loop over the [item, count] pairs with a compare on count. The total is O(n + m log k) for n items with m different values.

Heapify everything, then pop k

Build a max-heap of all n numbers in O(n) and pop k times, for O(n + k log n). It wins when k is close to n, but it needs every number in memory at once.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "k largest", "k smallest", "k most frequent", "k closest", "k-th largest", or "top k in a stream". If k is much smaller than n, the heap is the expected answer.
  • Say the backwards-sounding part clearly: "for the k largest I keep a min-heap, because the item I need to throw out is the smallest of my current group". Interviewers listen for that sentence.
  • Give the cost as O(n log k) time and O(k) space, compare it with sorting's O(n log n), and mention that the input can be a stream.
  • A common follow-up is "can you beat O(n log k)?". Answer: quickselect finds the k-th largest in O(n) on average, and one more pass collects the bigger items. But it needs the whole array, changes it, and has an O(n²) worst case.

Where frontend code uses it

The same idea in real UI code
  • A performance dashboard can show the 10 slowest requests out of a stream of thousands without keeping or sorting all of them.
  • Trending tags or the most-used emoji are the top k items by count.
  • A store locator shows the few closest stores to the user's location, ranked by distance.

Related algorithms