Running Median

 

Median is the middle element in the array (in sorted form).

The challange here is that we need to return the median in O(1) time.

Concept:

  1. We can maintain a sortted array.?  At each step sorting costs us nlog(n).
  2. We maintain 2 buckets of equal sizes. Left median contains all values less than a number k and the right median contains all values greater than k.

In 2nd method the insertion will be complex (and not O(1)), but we can easily compute the median in O(1).

To distribute numbers in 2 buckets, we can use 2 heaps. Max_heap (left bucket) and Min_heap (right bucket).

If the current number is lesse than max in max_heap_left, we can insert in max_heap_left, other wise we can insert it in min_heap_right.

This may create uneven sizes of heap, so we need to check in each step if the sizes are uneven, if yes… we need to fix it.

 

Here is the implementation in Python.
Note: Max heap is not supported in Python, so I used min_heap and inserted (and popped elements) by multiying the number by -1.

 

 


import heapq

def running_median(arr):

	max_heap_left = []
	min_heap_right = []

	for each in arr:

		if len(max_heap_left) == 0 or each  len(min_heap_right):
				popped_number = max_heap_left[0] * -1
				heapq.heappop(max_heap_left)
				heapq.heappush(min_heap_right, popped_number )
			else:
				popped_number = min_heap_right[0] 
				heapq.heappop(min_heap_right)
				heapq.heappush(max_heap_left, popped_number * -1)

	if len(max_heap_left) == len(min_heap_right):
		return (max_heap_left[0] * -1 + min_heap_right[0])/2.0
	else:
		if len(max_heap_left) > len(min_heap_right):
			return max_heap_left[0] * -1
		else:
			return min_heap_right[0]	

arr  = [1,2,3,4,5]

print running_median(arr)	
arr = [1,2,3,4,5,6]
print running_median(arr)	

Advertisements

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