The Best Structure

Hi,
What is the Best Structure for this goal!
the Add function in O(n) and fetch-meddian in O(1)?
Thanks!

a min-max heap!

http://forums.codeguru.com/

its add would take O(n) but for finding its Meddian you should pick the max and min number and divide them on 2 which would take in O(1)
//I'm not sure what is your meaning from fetch-median?

What is add function complexity? if it's one of adding of just one element, you can as well use simple sorted array, inserting new element by bubble sort and picking median as center element of that array. :)

I read it the same way as Robotact. A sorted array seems like the easiest solution.