I would like to use heaps to find a running median number. We have to start the algorithm with a initial set of numbers following which there can be a running process.
For example, if we start with the following array:
A = [4, 3, 2, 90, 16, 78]
we will be required to return the median of this array. What is the runtime of this process?
After this initial median, the algorithm should accept numbers, one or more at a time, and
return a median without redoing the heap building process or in linear time.
For example, we
could add numbers, 22 and 24, and your algorithm should return the median in a better than linear runtime. We can set a bound to the runtime of the algorithm so that the runtime does not exceed O(lg k) where k is the number of elements that are passed to the algorithm at each step. If we hand it 2 numbers the time taken to find the median should be O(lg 2), and so on.
Please note that the initial array could be different from the shown example.
( HINT: You will need two heaps for this to work in O(lg k) running time )