Find Median from Data Stream

'''
Maintain 2 heaps, first one(Max heap) should be containing left half of all the elements seen and put it into the sorted order and vice versa for other one(Min heap).

left_half and right_half can have either same size or left_half can have one element more.
so directly push a new element into the right_heap and then check is the right_heap size is greater than left or not, if greater then right_heap top will be having the smallest element of the right_half so pop that element and push it into the left heap,that's all.
While returning the median, if sum of length of both equal to even, return the mean of the top two elements of the heaps else return the left heap top element.
'''

from heapq import heappush, heappop
class MedianFinder:

    def __init__(self):
        self.left_heap = []   # max heap (store negative)
        self.right_heap = []  # min heap

    def addNum(self, num: int) -> None:
        # Step 1: push to max heap
        heappush(self.left_heap, -num)

        # Step 2: balance → move max of left to right
        heappush(self.right_heap, -heappop(self.left_heap))

        # Step 3: maintain size property
        if len(self.right_heap) > len(self.left_heap):
            heappush(self.left_heap, -heappop(self.right_heap))

    def findMedian(self) -> float:
        if len(self.left_heap) > len(self.right_heap):
            return -self.left_heap[0]
        else:
            return (-self.left_heap[0] + self.right_heap[0]) / 2