I would like you to use heaps to find a running median number. We will start the algorithm with
an 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]
you 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 )
Hello,
My name is Tinh Nguyen. I have done many projects in algorithm for worldwide students and got many positive feedbacks from them. You can check my profile for more detail.
http://freelancer.com/u/nani01029x.html
Let me help you. I'm about to get started right away. Looking forward to your reply.
Thanks and best regards,
Tinh Nguyen