#215HardHeaps· Two Heaps with Lazy Deletion

Sliding Window Median Feed

A trading dashboard receives one price per second and shows the median price of the most recent `k` seconds. Averages are distorted by a single spike, so the desk prefers the median. For a window of `k` prices, sort them. If `k` is odd the median is the middle price. If `k` is even there are two middle prices and the dashboard shows the lower one (the price at position `(k - 1) / 2` using integer division, counting from 0 in the sorted window). Given all prices and the window size `k`, return the median of every window: the first window holds prices `0..k-1`, the second `1..k`, and so on. The answer has `n - k + 1` values.

Input format

`values`: the prices in arrival order; `k`: the window size.

Output format

An array of `n - k + 1` integers: the lower median of every window.

Examples

Input: values = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Output: [1, -1, -1, 3, 5, 6]

The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7] with medians 1, -1, -1, 3, 5, 6.

Input: values = [5, 2, 2, 9], k = 2

Output: [2, 2, 2]

Each window has two prices and the lower one is reported: min(5,2)=2, min(2,2)=2, min(2,9)=2.

Input: values = [10, 20, 30, 40], k = 4

Output: [20]

A single window of four prices: sorted it is 10 20 30 40 and the lower middle price is 20.

Constraints

1 <= k <= values.length <= 10^5
-10^9 <= values[i] <= 10^9

#heap
#sliding-window
#lazy-deletion
#median
#data-stream