How to Calculate a Running Median in C++

1. Running Median
2. Calculation of a Running Median in C++

This is a tutorial on how to calculate the running median efficiently. We will start with a detailed description of the running median, followed by an algorithm and some implementation considerations.

Running Median

The running median is an efficient way of calculating a sequence of numbers. The intuition behind it is that if we are interested in the median, then we don’t need to know all of the values in the sequence, but instead, we can keep track of how many values are above or below it.

If there’s an even number of values, then we will take the average (or mean) for both halves and use that as our new middle value.

The running median starts with the observation in the middle of the sorted list. The next observation is compared to this middle observation; if it is larger or smaller, it becomes the new middle point.

This process continues until no more observations are left in the sorted list.

Calculation of a Running Median in C++

The running median is computed using two heaps. All values less than or equal to the current median are in the left heap.

All those greater than or equal to the current median are in the right heap.

The running median is updated by swapping each number in these two heaps. To maintain a constant number of swaps, we need a way to know when one of these two heaps becomes empty.

When one of these two heaps becomes empty, it means all values less than or equal to the current median have been processed, and all values greater than or equal to it have been processed. At this point, we can swap with a value from whichever heap is not empty, which will always be either the left heap or the proper heap, depending on which was emptied first.

We need a data structure that supports efficient insertion and deletion at both ends for this algorithm to work. This data structure should also be able to take advantage of cache locality.