Median of a dynamic list

Here, I discuss the problem of maintaining the running median of a list when numbers are added and removed from the list. The straightforward solution of keeping the list sorted takes constant time per median calculation but linear time per addition/deletion. It would be too slow for our purpose.

The case of addition can be handled by using heaps (a min heap and a max heap). We always insert in the min heap. At odd iterations, we check if the minimum element in the min heap is less than the maximum element in the max heap. If so, we swap the two elements. At even iterations, we remove the minimum element of the min heap and insert it into the max heap. The following constraint always holds on the sizes of the two heaps : “minHeap.size is always equal to or one greater than maxHeap.size”.

Median calculation is straightforward. If the total number of elements is odd, the minimum element in the min heap is the median, otherwise the average of the minimum element in the min heap and the maximum element in the max heap is the median. Thus, median calculation still takes constant time but now addition takes logarithmic time. Deletion still takes linear time because heaps support deletion from their top only. If we wanted to support only insertions, then this would be enough.

To handle deletions, we use indexed priority queues (basically heaps with indexing of keys) – a min indexed priority queue and a max indexed priority queue. An indexed priority queue supports deletion of any element in logarithmic time so we will be able to support deletions as well. Addition is similar to as with heaps. To delete an element, we find which priority queue it lies in and delete it from there. If required, we remove the top element from the other priority queue and insert it into this one to satisfy the constraints on the sizes of the two priority queues (MaxPQ.size <= MinPQ.size <= MaxPQ.size + 1 => MinPQ.size is equal to or one greater than MaxPQ.size). In this way, we support median calculation in O(1) and addition/deletion in O(log n).

Take a look at the Java implementation.

2 thoughts on “Median of a dynamic list

  1. Pingback: Indexed Min-Priority Queue C++ implementation | Everything Under The Sun

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s