The problem statement is pretty straightforward: given an array of integers and a window size, return an array of doubles of the median of each window.
$arr = 1, 3, 5, 10, 6, 9, 2$ and $k = 3$ would yield a result of $3, 5, 6, 9, 6$.
Using std::priority_queue (in C++) for the heap implementation, there's a minHeap and maxHeap. In a single iteration, insert the value entering our window in the correct heap, rebalance as necessary, add the median to the result (if the window is big enough), then remove the value which is leaving the window from whatever heap it's in: This could require moving all but 1 heap element to the other heap, then moving them back.
The lesson I saw this on actually inherits from priority queue and implements remove functionality: Linear search [O(k)], then removes the item [O(log k)]. It claims O(n * k) complexity as at each iteration the insertion is O(log k) and the search to remove is O(k). I assume in an interview extending a heap beyond it's traditional form is not only unnecessary but probably frowned upon.
I'm curious of the complexity at which the version w/o the direct removal would run. The O(n) part is obvious but the sub operations not as clear to me. A heap will generally have k/2 items in it. In the worst case you delete [O(log k)] and then insert [O(1)] each one. My mind is telling me O(n * k log k) but I wouldn't bet my house on it.
For the record: Not looking for an optimal solution - just the runtime of this one.
Insertion Algorithm:
We accept an integer n
as input.
- If
n
is smaller than the top element ofmaxHeap
, push it onmaxHeap
and go to step 3. - Push
n
onminHeap
. - If
maxHeap
's size is 2 or more thanminHeap
's size, move the top element ofmaxHeap
tominHeap
and go to step 5. - If
minHeap
's size exceedsmaxHeap
's size, move the top element ofminHeap
tomaxHeap
. - Stop the algorithm.
Obtaining The Median:
- If sizes of
minHeap
andmaxHeap
are the same, then return the arithmetic mean of their top elements and go to step 4. - If
maxHeap
's size exceedsminHeap
's size, return the top element ofmaxHeap
and go to step 4. - If
minHeap
's size exceedsmaxHeap
, return the top element ofminHeap
. - Stop the algorithm.
Removal Algorithm:
We accept an integer n
as input.
- If
num
is not greater than the top element ofmaxHeap
, remove the current top element frommaxHeap
and insert it tominHeap
, untiln
becomes the new top element ofmaxHeap
. Else skip to step 4. - Remove the top element of
maxHeap
. - Remove the current top element of
minHeap
and insert it tomaxHeap
, until the sizes ofminHeap
andmaxHeap
will differ by no more than 1. Go to step 7. - Remove the current top element from
minHeap
and insert it tomaxHeap
, untiln
becomes the new top element ofminHeap
. - Remove the top element of
minHeap
. - Remove the current top element of
maxHeap
and insert it tominHeap
, until the sizes ofminHeap
andmaxHeap
will differ by no more than 1. - Stop the algorithm.
Finding Sliding Window Median:
We accept an array of integers arr
, and an integer k
as input.
- Set
left
to $0$. Setright
to $0$. Setresult
to $0$. - Insert (by using Insertion Algorithm above) the element of
arr
with indexright
. - If
k-1
is not greater thanright
, add median (found by Obtaining The Median algorithm above) toresult
. Else go to step 6. - Remove the element of
arr
with indexleft
. - Add $1$ to
left
. - If
right
is less than the greatest index ofarr
, add $1$ toright
and go to step 2. - Return the current value of
result
and stop the algorithm.
This last algorithm is where the mystery is. Worst case we have is to remove a number at the bottom of a $k/2$ sized heap. Would that be $\log k$ for $k/2$ operations then $O(1)$ for $k/2-1$ operations?
the version w/o the direct removal
explicitly? I don't "see" it. $\endgroup$