Matsushita's Blog

Heaps: Find the Running Median


This problem is that we calculate median of array the range is from 0 to ith.


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.

Source Code