Make delicious recipes!

Find median of an unsorted growing array

(You can store all the elements)

Median is defined as the middle element if no of elements is odd, else its the average of two middle elements.

Finding a median makes sense only if the array is sorted.

But we cannot sort the array just to find the median.

Keeping track of max and min during insertion/removal will also not help because max/min will not tell us the order of the remaining elements.


Solution: Maintain 2 heaps - max heap and min heap.

Max heap has bigger elements on top while min heap has lower elements.

Whenever, a new element is added to the growing array, compare it with the current median.
If its smaller than the current median, add it to the max heap.
If its larger than the current median, add it to the min heap.


Make sure that the 2 heaps always have half the number of elements.
If they do not have equal number of elements, then transfer from bigger heap to smaller.


By doing this exercise, we are diving the elements into two halves around the current median.
One half contains max-heap of elements smaller than current median.
Other half contains min-heap of elements greater than current median.

If 2 such heaps are maintained, then:

  1. For odd number of elements, the heaps will differ by size of 1 and the topmost element of the bigger heap is the median.

  2. For even number of elements, the heaps will be equal in size and the average of their topmost elements is the median.




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal