Heaps: Find the Running Median
Problem
This problem is that we calculate median of array the range is from 0 to i
th.
Solution
By using Two Priority Queues: minHeap and maxHeap, we can solve this problem. The roles of them are following.
- minHeap : To store bigger half values in array.
- maxHeap: To store smaller half values in array.
In this case, the root value of minHeap and the root value of maxHeap are medians. The points is that which heap should we add each element and we have to keep the balance of two heaps size.