medianbinary-heap

find median of a unsorted array using heap

Is there a way to find median of a unsorted array using heap ? If it is possible, is it more efficient than using sorting and then finding median ?

Solution

  • The trick here is to use two heaps of which one is min-heap and other is max-heap. I will not go in details, but the following points are sufficient to implement the required algorithm.

    1. The top of the min-heap is the smallest element greater than or equal to the mean
    2. The top of the max-heap is the largest element less than or equal to the mean.

    Now coming to your second question, it is only efficient if you want to find the running median i.e. the median just after inserting a new element each time into the array.

    If you want to calculate the median of all the array elements just once, then sorting will be a good idea.

    Hope this helps.