Write RunningMedian: after each number read, print the median of all numbers so far (for an even count, the average of the two middle values).
Keep two heaps: low, a max-heap with the smaller half, and high, a min-heap with the larger half. Insert into the right one, then rebalance so that low has as many elements as high or one more. The median is then on top.
For the input
5 15 1 3 8 7
the program prints
add 5 -> median 5.0 (low 1, high 0)
add 15 -> median 10.0 (low 1, high 1)
add 1 -> median 5.0 (low 2, high 1)
add 3 -> median 4.0 (low 2, high 2)
add 8 -> median 5.0 (low 3, high 2)
add 7 -> median 6.0 (low 3, high 3)
Top of low: 5, top of high: 7