Keep track of median. Use min heap and max heap. During insertion if number is greater than median, insert into the min heap. If the number is less than the median, insert into the max heap. Delete/insert/replace median if heap size differs by more than 1. Or use a mmm-heap (min-max-median heap).