Kth largest in a stream

Keep a min-heap holding exactly the k largest values seen so far.

on arrival x:
    if heap.size < k:
        heap.push(x)
    elif x > heap.top():
        heap.pop(); heap.push(x)
    return heap.top() if heap.size == k else undefined

Why a min-heap. The answer is the smallest of the k largest values. A min-heap puts exactly that element at the top, so the query is O(1). It also makes eviction correct: when a new value arrives, the element that should be dropped is the weakest of the current top k, which is again the root. A max-heap would put the largest value at the top — the one you never want to touch — and finding the element to evict would cost a linear scan.

O(log k) per arrival, O(k) space, independent of stream length. That independence is the whole reason the structure is chosen.

Before k elements have arrived there is no kth largest; say what you return then rather than letting it be undefined behaviour.

If duplicates each count separately, this is already correct. If the kth distinct value is wanted, the heap needs a companion set and the eviction rule changes — worth flagging as a clarifying question rather than assuming.