LC 295数据流的中位数Find Median from Data Stream　困难

设计数据结构支持不断添加整数，并随时取出已读入全部数字的中位数。

思路 对顶堆：heappushpop 归位到对面堆，保持 small（存相反数）多 0/1 个；取中位数看两堆顶。add/查询 O(log n)/O(1)。

class MedianFinder:
    def __init__(self):
        self.small = []  # 较小一半，存相反数
        self.large = []  # 较大一半

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

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