Kth Largest Element in a Stream

Kth Largest Element in a Stream is the classic introduction to the heap (priority queue). It teaches a counterintuitive trick: to track the largest values, you lean on a min-heap — and to keep only the top k, you throw away the smallest whenever the pile grows too big.

The slow way first

The obvious idea: keep every number in a list, and on each add sort the whole list and read the kth element from the end. That works, but sorting is O(n log n) per call — and the stream can be huge. We are re-sorting numbers we already sorted a moment ago.

The question to ask: do I actually need all n numbers in order? No. I only ever care about the k largest, and within those, only the smallest one (that smallest-of-the-top-k is the kth largest). Everything below it is irrelevant.

The idea: a min-heap of size k

Keep a min-heap holding at most k elements — the k largest values seen so far. A min-heap keeps its smallest element at the root, reachable in O(1). On each add: push the new value, and if the heap now holds more than k elements, pop the smallest. Whatever survives at the root is the kth largest.

The key insight: a min-heap lets the smallest of our keepers fall out cheaply. Any incoming value smaller than the current root can never crack the top k, so it gets pushed and popped right back out. A value bigger than the root bumps the old root and a new, larger minimum settles in.

Walk through it

Step through the animation. We seed the heap with 4, 5, 8 — the root settles to 4, the 3rd largest. Then add(3) pushes 3, the size hits 4, and we pop the smallest (3 itself) — the answer stays 4. Then add(10) pushes 10, size hits 4 again, and this time popping the smallest removes the old root 4; the heap re-settles with 5 on top, so the answer climbs to 5.

Pseudocode

keep a min-heap; remember k
on init: for each starting number, call add(number)
 
add(val):
    push val onto the heap
    if heap size > k:
        pop the smallest element
    return the root (the heap's smallest) = the kth largest

The Python solution

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []
        for n in nums:
            self.add(n)
 
    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

• self.heap is a Python list managed as a min-heap by the heapq module — index 0 is always the smallest.
• The constructor just replays add over the starting numbers, so all the logic lives in one place.
• Line 9 pushes the new value in O(log k).
• Lines 10 and 11 trim the heap back to size k by popping the smallest — this is what keeps only the top k.
• Line 12 returns self.heap[0], the root, in O(1). Because the heap holds exactly the k largest values, its minimum is the kth largest.

Complexity

We only ever store k elements, so the heap uses O(k) space, and each add costs O(log k) — independent of how long the stream gets. Reading the answer is O(1). That trade — a bounded min-heap to track the top k — shows up across streaming and top-k problems.

When this pattern shows up

Practice