Running Median - Question 4 Answers

4

Invoking the function below at line 7 of the pseudo code will modify the algorithm to track a sliding window of 100 values.

\begin{algorithm}
\caption{Sliding Window Running Median}
\begin{algorithmic}
\REQUIRE min-heap, max-heap
\REQUIRE window = queue data structure to track the sliding window (a linked list would also work)
\REQUIRE value = value to append
\FUNCTION{maintainSlidingWindow}{min-heap, max-heap, window, value}
    \STATE \CALL{Enqueue}{window, value}
    \IF{$\vert \text{window} \vert \leq 100$}
        \RETURN
    \ENDIF
    \STATE
    \STATE doomed $\gets$ \CALL{Dequeue}{window}
    \IF{doomed $\leq$ \CALL{heapPeek}{max-heap}}
        \STATE \CALL{heapDelete}{max-heap, doomed}
    \ELSE
        \STATE \CALL{heapDelete}{min-heap, doomed}
    \ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Return to Exercises