Given a sequence of integers, print the median for each non-empty prefix of the sequence.

Input. The input consists of one or more sequences. Each sequence consists of integers separated by space. Each sequence is terminated by a new line character (\n). The input is terminated by EOF. Consider the following example.

1 7 6 8 9
-4 -3 -2 -1


Output. The output consists of one output sequence for each input sequence. Each output sequence consists of one real number for each non-empty prefix of the corresponding input sequence. Each real number is the median of the corresponding prefix. Each real number is formatted with one decimal after the decimal point. Each output sequence is terminated by a new line character (\n). The output is terminated by EOF. The following example corresponds to the example input.

1.0 4.0 6.0 6.5 7.0
-4.0 -3.5 -3.0 -2.5


Before you read our solution, try to solve the problem on your own. Remember that practice makes perfect.

2018-07-09 The Book of Problems currently supports Ruby, Python, Elixir, Java, C, OCaml, and now C++!

# Approach

We track the median by means of a pair of heaps. As we read the sequence, we keep the lower half of the elements in a max-heap and the upper half in a min-heap. For every non-empty prefix, the median is either the root of one heap or the average of both roots.

We illustrate our approach by example. Consider the following sequence and the min-heap and max-heap after reading each element from left to right.

 element: 1 7 6 8 9 2 3 0
-----------------
min-heap:               9
9 9 8
8 9 8 8 7
7 7 7 8 7 7 6 <-- root
-----------------
max-heap: 1 1 6 6 7 6 6 3 <-- root
1 1 6 2 3 2
1 1 2 1
1 0


When we read an element, we place it in max-heap when it is less or equal to the root, otherwise we place it in the min-heap. For example, 1 goes to the max-heap and 7 goes to the min-heap.

The crucial aspect of our approach is that we satisfy the following condition at every moment: max-heap is at least as big as min-heap and at most one element more than min-heap. To satisfy the condition, we balance the heaps when they become unbalanced. Consider the case when the min-heap becomes bigger than the max-heap after reading 9.

 element: 1 7 6 8 9 2 3 0
-----------------
min-heap:
9
8 8
7 7 7 7       <-- root
-----------------
max-heap: 1 1 6 6 6       <-- root
1 1 1


In this case, we balance the heaps by popping the root of min-heap and pushing it into the max-heap. Consider the situation where the max-heap becomes bigger than min-heap by more than one element after we read 0.

 element: 1 7 6 8 9 2 3 0
-----------------
min-heap:           9 9 9
8 9 8 8 8
7 7 7 8 7 7 7 <-- root
-----------------
max-heap: 1 1 6 6 7 6 6 6 <-- root
1 1 6 2 3 3
1 1 2 2
1 1
0


In this case, we balance the heaps by popping the root of the max-heap and pushing it into the min-heap.

We compute the median in the following way. When the max-heap is larger than the min-heap, the median is the root of the max-heap. When both heaps are the same size, the median is the average of both roots.

The run time of the approach is dominated by the repeated insertion & removal of elements from both heaps. Each such operation takes $O(\text{log}\,n)$, where $n$ is the length of the sequence. The count of those operations is linear on the length of the sequence, for that reason the time complexity of the approach is $O(n\,\text{log}\,n)$.

# Ruby Implementation

We implement our approach in Ruby as follows.