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

# -*- coding:utf-8 -*-
class Solution:
    record=[]
    record_min=[] # dagen
    record_max=[] # xiaogen
    def Insert(self, num):
        self.record.append(num )
        # 形成一个小跟堆
        # 每次先往min里面放一个
        self.record_min.append(num)
        for i in range(len(self.record_min),-1,-1):
            self.makeheap_min(i)
        # 插入之后，把最大的弹过去
        tmp=self.record_min[0]
        self.record_min[0]=self.record_min[-1]
        self.record_min.pop(-1)
        self.makeheap_min(0)
        self.record_max.insert(-1,tmp)
        for i in range(len(self.record_max),-1,-1):
            self.makeheap_max(i)
        # 如果min比max少一个，就把max中最小的弹回来
        if len(self.record_min)-len(self.record_max)<0:
            tmp=self.record_max[0]
            self.record_max[0]=self.record_max[-1]
            self.record_max.pop(-1)
            self.makeheap_max(0)
            self.record_min.insert(-1,tmp)
            for i in range(len(self.record_min),-1,-1):
                self.makeheap_min(i)





        # write code here
    def GetMedian(self):
        # write code here
        if len(self.record)%2==0:
            # oushu
            return (self.record_max[0]+self.record_min[0])/2
        else:
             return self.record_min[0]

        

    def makeheap_max(self,idx): # xiaogen
        maxNode=len(self.record_max)-1
        l=2*idx+1
        r=2*idx+2
        if l>maxNode:
            return
        elif r>maxNode:
            if self.record_max[idx]>self.record_max[l]: # 互换位置
                tmp=self.record_max[idx]
                self.record_max[idx]=self.record_max[l]
                self.record_max[l]=tmp
                self.makeheap_max(l)
        else:
            if self.record_max[l]<=self.record_max[r]:
                if self.record_max[l]>self.record_max[idx]:
                    return
                else:
                    tmp=self.record_max[idx]
                    self.record_max[idx]=self.record_max[l]
                    self.record_max[l]=tmp
                    self.makeheap_max(l)
            else:
                if self.record_max[r]>self.record_max[idx]:
                    return
                else:
                    tmp=self.record_max[idx]
                    self.record_max[idx]=self.record_max[r]
                    self.record_max[r]=tmp
                    self.makeheap_max(r)

    def makeheap_min(self,idx): # dagen
        maxNode=len(self.record_min)-1
        l=2*idx+1
        r=2*idx+2
        if l>maxNode:
            return
        elif r>maxNode:
            if self.record_min[idx]<=self.record_min[l]: # 互换位置
                tmp=self.record_min[idx]
                self.record_min[idx]=self.record_min[l]
                self.record_min[l]=tmp
                self.makeheap_min(l)
        else:
            if self.record_min[l]>=self.record_min[r]:
                if self.record_min[l]<self.record_min[idx]:
                    return
                else:
                    tmp=self.record_min[idx]
                    self.record_min[idx]=self.record_min[l]
                    self.record_min[l]=tmp
                    self.makeheap_min(l)
            else:
                if self.record_min[r]<=self.record_min[idx]:
                    return
                else:
                    tmp=self.record_min[idx]
                    self.record_min[idx]=self.record_min[r]
                    self.record_min[r]=tmp
                    self.makeheap_min(r)