题解 | #数据流中的中位数#

# -*- coding:utf-8 -*-
import heapq

class Solution:
    def __init__(self):
        # 最小堆，保存较大的一半元素
        self.min_heap = []
        # 最大堆，保存较小的一半元素，最大堆使用负数存储
        self.max_heap = []

    def Insert(self, num):
        # 插入时首先考虑插入到最大堆（保存较小一半的元素）
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)
        
        # 保持两个堆的平衡
        if len(self.max_heap) > len(self.min_heap) + 1:
            # 如果最大堆比最小堆多两个以上元素，将堆顶元素移动到最小堆
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap):
            # 如果最小堆比最大堆多，移动堆顶元素到最大堆
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def GetMedian(self):
        # 如果两个堆大小相等，中位数为两个堆顶元素的平均值
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            # 否则，中位数为元素较多的那个堆的堆顶元素
            return -self.max_heap[0]