Kth Largest Element in a Stream

Design a structure that, given an initial list of numbers, supports adding new numbers one at a time and always answering "what is the k-th largest number seen so far?"

Example

k = 3, initial 4 5 8 2. Adding 3, 5, 10, 9, 4 in order returns 4, 5, 5, 8, 8.

Approach

Keep a min-heap of size exactly k holding the k largest values seen so far — its smallest element (the heap root) is always the answer. Adding a number: push it, and if the heap grows past size k, pop the smallest. Each add is O(log k), independent of how many numbers have streamed through in total.

Input format

Line 1: k Line 2: the initial numbers, space-separated Line 3: number of values to add, q Line 4: the q values to add, in order, space-separated

Print the k-th-largest value after each add, space-separated.