Running Median Problem

Finding the median as elements are inserted

Brute Force

• Use a sorted array
• Access the middle element or the average of the two middle elements if even length
• $O(n^2)$ time

Smart

• Uses two Binary Heaps
• $O(\log n)$ time

lowers = Max heap // stores elements to the left of median
highers = Min heap // stores elements to the right of median
 
// 1. Adding an Element, e: 
if lowers.size = 0 or e < lowers.root:
	lowers.add(e)
else
	highers.add(e)
		
// 2. Rebalancing:  
Find biggerHeap and smallerHeap from highers and lowers
if (biggerHeap.size - smallerHeap.size) = 2:
	smallerHeap.add(biggerHeap.extractMin())
 
// 3. Returning Median:  
if size of both heaps are equal:
	return (lowers.max + highers.min)/2 else
return the root of bigger heap (lowers.max or higher.min)