LeetCode 295 Find Median from Data Stream - Implementation

Max-heap for smaller half, min-heap for larger half. Keep balanced.

class MedianFinder: def init(self): self.small = [] # max-heap (use negative) self.large = [] # min-heap

def addNum(self, num):
    heappush(self.small, -num)
    heappush(self.large, -heappop(self.small))
    if len(self.large) > len(self.small):
        heappush(self.small, -heappop(self.large))

def findMedian(self):
    if len(self.small) > len(self.large):
        return -self.small[0]
    return (-self.small[0] + self.large[0]) / 2

$O(\log n)$ add, $O(1)$ findMedian, $O(n)$ space.