Finding the Kth largest element in a stream of integers

Keep a min-heap containing the k largest values seen so far. On each new number, push it; if the heap grows beyond k, pop its minimum. Once at least k values have arrived, the heap top is exactly the kth largest because every value outside the heap is no greater than that minimum and the heap holds k values no smaller than it. This is preferable to a max-heap of every element or sorting the stream repeatedly. Clarify what add should return before k elements exist, perhaps null or the current minimum, according to the API. Test k one, duplicate values, negative values, an initial list shorter than k, and a long stream. Each addition is O(log k) time and memory is O(k), compared with O(n) storage for retaining the whole history. If k changes dynamically, the bounded-heap invariant needs a different structure or rebuilding.