DiffPush Tier Heaps · Hard Problems O(log k) per append · O(k)
A trading floor's ticker appends new prices continuously, and the desk's display must show the kth-highest price after every append — it cannot re-sort a growing history on each tick. The display keeps a small pen holding only the k highest prices seen so far; each append either joins the pen or is discarded, and the pen's weakest resident is always the current kth-highest.
Input: An integer k, the initial array nums, and a list of appended values.
Output: Return the list of kth-largest values after each append, in order.
1 <= k <= 10^40 <= nums.length <= 10^4-10^4 <= values <= 10^4At most 10^4 appendsInput: {"k":3,"initial":[4,5,8,2],"adds":[3,5,10,9,4]}
Output: [4,5,5,8,8]
Each append reshuffles the pen of the three highest prices; its weakest resident is reported.
Input: {"k":1,"initial":[],"adds":[-3,-2,-4,0,4]}
Output: [-3,-2,-2,0,4]
With k=1 the display simply tracks the running maximum.