Top-K from a Stream

top-k-streamproblem-labheapmin-heapstream

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Top-K from a Stream

Data Challenges

To keep the k largest values from an unbounded stream, push each value into a min-heap and pop the minimum whenever the heap grows past size k. The smallest of the kept values stays on top, so any new value only displaces it if it is larger.

The scenario: values stream in without end and you need the k largest seen so far, without storing the whole stream.

A bounded min-heap of size k holds the current top k. Push each incoming value, then if the heap exceeds k, pop the minimum.

Because the smallest kept value is always on top, a new value either evicts that minimum (it was larger) or is itself popped (it was not), so the heap always retains exactly the k largest.

Push every streamed value into the heap.

Pop the minimum when size exceeds k.

The heap retains exactly the k largest values.

class MinHeap {
  constructor() {
    this.data = []
  }
  push(v) {
    this.data.push(v)
    this.data.sort((a, b) => a - b)
  }
  pop() {
    return this.data.shift()
  }
  get size() {
    return this.data.length
  }
}

function topK(stream, k) {
  const heap = new MinHeap()
  for (const v of stream) {
    heap.push(v)
    if (heap.size > k) {
      heap.pop()
    }
  }
  return heap.data
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Bounded min-heap

A min-heap whose smallest element sits on top is the core of the solution.

const heap = new MinHeap()

2. Push each value

Every value from the stream is pushed in as it arrives.

heap.push(v)

3. Bound the size

Whenever the heap exceeds k, the excess element is removed.

if (heap.size > k) {

4. Pop the minimum

Popping the minimum discards the smallest, so only the k largest survive.

heap.pop()

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.