Running Median - Question 4 Answers


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

\caption{Sliding Window Running Median}
\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$}
    \STATE doomed $\gets$ \CALL{Dequeue}{window}
    \IF{doomed $\leq$ \CALL{heapPeek}{max-heap}}
        \STATE \CALL{heapDelete}{max-heap, doomed}
        \STATE \CALL{heapDelete}{min-heap, doomed}

Return to Exercises