The median of a set of values is the value that is larger than half of them and smaller than the other half. For example, the median of 3 4 1 5 9 2 6 is 4.

To compute the median, you can of course put the set into a list, sort it, and pick the middle one. But there is a more efficient way.

Use two priority queues, one for the values that are lower than the median, and one for those that are higher. The first one needs its comparison reversed, so that the “highest priority” is the largest value. When adding a new value, check whether it is smaller or larger than the median, and add it to one or the other priority queue. Then check the sizes of the queues. If they differ by more than one, add the current median to the smaller one and replace it with the highest priority element of the other.