Streaming kth Largest Element

Keep only the k largest values seen so far, discarding anything smaller than the smallest of those k.

A heap lets you find and remove the current minimum of the kept set quickly.

1. 1. Maintain a bounded min-heap

   Keep a min-heap holding the $k$ largest elements seen so far; the heap's root is always the smallest of these $k$ elements.

2. 2. Process each new element

   For each new value, compare it to the heap's root; if larger, replace the root and re-heapify. Each of the $n$ elements costs $O(\log k)$, giving $O(n\log k)$ total.

Answer: A min-heap of size k.