Решить задачу Find Median from Data Stream (LeetCode 295)?

LeetCode 295. Поток чисел, поддерживать median за O(log n) per add. Два heap-а: max-heap для lower half, min-heap для upper half.

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (через negative)
        self.hi = []   # min-heap

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.lo) < len(self.hi):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

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

Инвариант: lo хранит lower half, hi — upper half; lo может быть на 1 больше. addNum: push в lo → pop из lo в hi (балансировка), при необходимости вернуть один в lo. Median: нечётное — top of lo; чётное — average двух tops. Brute force — sorted insertion O(n). Связанные: Sliding Window Median (480) — нужно remove из heap (lazy deletion).