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

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def __init__(self):
        self.hpBigger = []
        self.hpSmaller = []
        heapq.heapify(self.hpBigger)
        heapq.heapify(self.hpSmaller)
    def Insert(self, num):
        # write code here
        if self.hpSmaller == [] or num < -self.hpSmaller[0]:
            heapq.heappush(self.hpSmaller, -num)
            if len(self.hpSmaller) - len(self.hpBigger) > 1:
                pop = heapq.heappop(self.hpSmaller)
                heapq.heappush(self.hpBigger, -pop)
        else:
            heapq.heappush(self.hpBigger, num)
            if len(self.hpBigger) - len(self.hpSmaller) > 1:
                pop = heapq.heappop(self.hpBigger)
                heapq.heappush(self.hpSmaller, -pop)
                
    def GetMedian(self):
        # write code here
        if len(self.hpSmaller) - len(self.hpBigger) == 1:
            return -self.hpSmaller[0]
        elif len(self.hpBigger) - len(self.hpSmaller) == 1:
            return self.hpBigger[0]
        else:
            return (-self.hpSmaller[0] + self.hpBigger[0]) / 2