import heapq
class MedianFinder:
def __init__(self):
self.max_heap = [] # 极大堆(python都是极小堆，因此是负数进入). 数据中小的一半进入max_heap
self.min_heap = [] # 数据中大的一半进入min_heap
def addNum(self, num: int) -> None:
if not self.max_heap or num <= -self.max_heap[0]: # -max_heap[0] 是小数据中的最大值
# 多一个的奇数的话，进入max_heap. findMedian奇数的话就从max_heap中取
heapq.heappush(self.max_heap, -num)
if len(self.max_heap) - len(self.min_heap) > 1:
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
else:
heapq.heappush(self.min_heap, num)
if len(self.max_heap) < len(self.min_heap):
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
def findMedian(self) -> float:
if len(self.max_heap) == len(self.min_heap):
return (-self.max_heap[0] + self.min_heap[0]) / 2.0
return -self.max_heap[0]