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

Check your solution online

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

Click here to check your solution online at The Book of Problems.

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.

#!/usr/bin/env ruby

class BaseHeap
  def initialize
    @data = []
  end

  def push v
    @data.push v
    bubble(@data.length - 1)
  end

  def pop
    last = @data.pop
    return last if @data.empty?
    root = @data[0]
    @data[0] = last
    sink 0
    return root
  end

  def peek
    @data.first
  end

  def size
    @data.length
  end

  def to_s
    inspect
  end

  def inspect
    @data.inspect
  end

  private

  def bubble i
    while 0 < i
      p = parent i
      return if ordered? p, i
      swap p, i
      i = p
    end
  end

  def sink i
    while true
      l = left i
      return if l >= @data.length
      r = right i
      if r >= @data.length || ordered?(l, r)
        pivot = l
      else
        pivot = r
      end
      return if ordered? i, pivot
      swap i, pivot
      i = pivot
    end
  end

  def parent i
    (i - 1) / 2
  end

  def left i
    (i * 2) + 1
  end

  def right i
    left(i) + 1
  end

  def swap i, j
    t = @data[i]
    @data[i] = @data[j]
    @data[j] = t
  end
end

class MinHeap < BaseHeap
  def ordered? i, j
    @data[i] <= @data[j]
  end
end

class MaxHeap < BaseHeap
  def ordered? i, j
    @data[i] >= @data[j]
  end
end

class PrefixMedian
  def initialize
    @left = MaxHeap.new
    @right = MinHeap.new
  end

  def push v
    if @left.size == 0
      @left.push v
      return
    end     
    if @left.peek < v
      @right.push v
    else
      @left.push v
    end
    balance
  end

  def median
    return nil if @left.size == 0
    return @left.peek.to_f if @left.size != @right.size
    return (@left.peek + @right.peek) / 2.0
  end

  private

  def balance
    if @left.size < @right.size
      @left.push @right.pop
    elsif @left.size > @right.size + 1
      @right.push @left.pop
    end
  end
end

while true
  input = readline.strip.split(' ').map(&:to_i) rescue break
  pm = PrefixMedian.new
  input.each_with_index do |v, i|
    pm.push v
    print pm.median
    print ' ' if i < input.length - 1
  end
  puts
end

Want to read more?

I love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments