k-th largest element in a price stream

Values arrive one at a time. For a fixed k chosen up front, after each add(x) report the k-th largest value seen so far.

k = 2
add(5) -> (only one value yet)
add(3) -> 3      # 2nd largest of {3, 5}
add(8) -> 5      # 2nd largest of {3, 5, 8}
add(9) -> 8      # 2nd largest of {3, 5, 8, 9}

Support add in $O(\log k)$. Re-sorting per tick is $O(n \log n)$; a full max-heap of everything wastes $O(n)$ space.