Kth largest in a stream, with a size-k min-heap

Keep only the k largest scores in a min-heap. The smallest of those k sits at the root, and the smallest of the top k is the kth largest. When a new score pushes the heap past k, throw away the root, since it can never be in the top k again.

Try:
CALL
1 / 1

Code

The highlighted line runs next. Sift-up and sift-down steps happen inside the library's push and pop, so they stay on the push and pop lines.

Min-heap (self.heap)

tree view every parent ≤ its children, so the smallest value is always on top

array view how the heap is really stored: children of index i are 2i+1 and 2i+2

Stream

Calls and what each one returns

all scores so far, largest first blue = kept in heap · green = kth largest · struck = dropped

Why it works: a dropped score has at least k bigger scores above it, so it can never be the kth largest again. Each add costs O(log k) and the heap never holds more than k+1 items.

Dry-run trace

Every step as a row. Click a row to jump there.

#ActionCallDetailheap (array)size

Keyboard: ← → step, Space play or pause. Limits: k ≤ 8, up to 10 numbers in nums and 10 adds. Real libraries may order the heap array slightly differently, but the root is always the same.