runningmedian.py

#!/bin/python3

import sys

def left(x):
    return 2*x + 1

def right(x):
    return 2*x + 2

def parent(x):
    return (x-1)//2

class Heap:
    def __init__(self, isMax):
        self.data = []
        self.isMax = isMax
        
    def _in_order(self, first, second):
        if self.isMax:
            return self.data[first] >= self.data[second]
        else:
            return self.data[first] <= self.data[second]
    
    def first(self, a, b):
        if a >= len(self.data) and b >= len(self.data):
            return None
        if a >= len(self.data):
            return b
        if b >= len(self.data):
            return a
        return a if self._in_order(a,b) else b
    
    def _swap(self, a, b):
        self.data[a], self.data[b] = self.data[b], self.data[a]
    
    def add(self, d):
        self.data.append(d)
        x = len(self.data)-1
        while x > 0 and not self._in_order(parent(x), x):
            self._swap(x, parent(x))
            x = parent(x)
      
    def __len__(self):
        return len(self.data)
    
    def top(self):
        return self.data[0]
    
    def extract_top(self):
        top = self.top()
        self.data[0] = self.data[-1]
        del self.data[-1]
        x = 0
        l = len(self)
        while True:
            nx = self.first(left(x), right(x))
            if nx is not None and not self._in_order(x, nx):
                self._swap(x, nx)
                x = nx
            else:
                break
        return top
            
class RunningMedianList:
    def __init__(self):
        self.upper = Heap(isMax=False)
        self.lower = Heap(isMax=True)
    
    def __len__(self):
        return len(self.upper) + len(self.lower)
    
    def median(self):
        if len(self) == 0:
            return None
        elif len(self) % 2 == 1:
            return self.upper.top() if len(self.upper) > len(self.lower) else self.lower.top()
        else:
            assert(len(self.upper) == len(self.lower))
            return 0.5 * (self.upper.top() + self.lower.top())
    
    def add(self, d):
        # Add to upper first when initializing the list.
        if len(self) == 0:
            self.upper.add(d)
        elif d > self.median():
            if len(self.upper) > len(self.lower):
                self.lower.add(self.upper.extract_top())
            self.upper.add(d)
        else:
            if len(self.lower) > len(self.upper):
                self.upper.add(self.lower.extract_top())
            self.lower.add(d)
                
n = int(input().strip())
values = RunningMedianList()
for _ in range(n):
   v = int(input().strip())
   values.add(v)
   print("%.1f" % values.median())