マツシタのお勉強

Heaps: Find the Running Median

Problem

www.hackerrank.com

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

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.

Source Code