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:
For
odd number of elements, the heaps will differ by size of 1 and the
topmost element of the bigger heap is the median.
For
even number of elements, the heaps will be equal in size and the
average of their topmost elements is the median.
|
