datastream-median

Find Median in Datastream

Solution 1: Two heaps

def __init__(self):
    self.hi = []  # min heap
    self.lo = []  # max heap
 
def addNum(self, num: int) -> None:
    # ensures len(self.hi) >= len(self.lo)
    if len(self.hi) == len(self.lo):
        heappush(self.lo, -num)
        heappush(self.hi, -heappop(self.lo))
    else:
        heappush(self.hi, num)
        heappush(self.lo, -heappop(self.hi))
 
def findMedian(self) -> float:
    if len(self.hi) == len(self.lo):
        return (self.hi[0] - self.lo[0]) / 2
    else:
        return self.hi[0]