Median of a growing array - PrismoSkills
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:
Read full article from Median of a growing array - PrismoSkills
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.
Read full article from Median of a growing array - PrismoSkills
