Let's see an application of $($binary$)$ heap. You are given an array A with $n$ integers, and

another integer $k,1kn.$ The numbers in A are either $-1$ or a positive integer, and you may

assume that all positive integers are distinct $($but there could be multiple $-1$ s $).$ You are asked to

design data structures and algorithm to produce an output array $x.$ Your algorithm should process

the numbers in A one by one: when a positive number is met, you put it to the end of $x$; if a $-1$ is

met, you need to remove the $k-$th smallest number in $x.$ You may also assume that, you will never

meet a $-1$ if the size of the current $x$ is smaller than $k.$ For example, if $A=[4,2,-1,7,3,8,-1,6]$

and $k=2,$ the output $x$ should be $x=[2,7,8,6].$

Design an algorithm to complete this task and analyze its running time. Your algorithm should run

in $O(nlogn)$ time. $($Hint: consider using two binary$-$heaps, one max$-$heap and one min$-$heap; the

max$-$heap maintains the smallest $k$ numbers in $x$ and the min$-$heap maintains rest of the numbers.$)$