数据流中位数-堆

'''老老实实本本分分用两个堆来实现'''
class Solution:
    def __init__(self):
        self.minNums=[] # 小根堆，其实存放的是最大的一半的数
        self.maxNums=[] # 大根堆，其实存放的是最小的一半的数
    def maxHeapInsert(self,num):
        self.maxNums.append(num) 
        i = len(self.maxNums)-1
        while i > 0 :
            if self.maxNums[i]>self.maxNums[(i-1)//2]:
                       # 堆的调整，如果加入的数大于其父节点的数，则交换位置
                t = self.maxNums[(i-1)//2]
                self.maxNums[(i-1)//2] = self.maxNums[i]
                self.maxNums[i] = t
                i = (i-1)//2 # 调整后的位置
            else: 
                break
    def maxHeapPop(self):
        t = self.maxNums[0] # 返回根节点，大根堆最大值
        self.maxNums[0] = self.maxNums[-1]
        self.maxNums.pop()
        lens = len(self.maxNums)
        i = 0
        while 2*i+1<lens:
            nexti = 2*i+1 #获得左孩子
            # 判断右孩子，选择最大的孩子节点值，交换位置
            if (nexti + 1 < lens) and self.maxNums[nexti + 1] > self.maxNums[nexti]:
                nexti +=1
            if self.maxNums[nexti]>self.maxNums[i]:
                tmp = self.maxNums[i]
                self.maxNums[i] = self.maxNums[nexti]
                self.maxNums[nexti] = tmp
                i = nexti
            else:break
        return t
    
    
    def minHeapInsert(self,num):
        self.minNums.append(num)
        lens = len(self.minNums)
        i = lens - 1
        while i > 0:
            if self.minNums[i] < self.minNums[(i - 1) // 2]:
                t = self.minNums[(i - 1) // 2]
                self.minNums[(i - 1) // 2] = self.minNums[i]
                self.minNums[i] = t
                i = (i - 1) // 2
            else:
                break
    def minHeapPop(self):
        t = self.minNums[0]
        self.minNums[0] = self.minNums[-1]
        self.minNums.pop()
        lens = len(self.minNums)
        i = 0
        while 2*i+1<lens:
            nexti = 2*i+1
            if (nexti+1<lens) and self.minNums[nexti] > self.minNums[nexti+1]:
                nexti += 1
            if self.minNums[nexti]<self.minNums[i]:
                tmp = self.minNums[i]
                self.minNums[i] = self.minNums[nexti]
                self.minNums[nexti] = tmp
                i = nexti
            else:
                break
        return t
    
    def Insert(self,num):
        if (len(self.minNums)+len(self.maxNums))&1==0:
            #长度为偶数,将大顶堆最大数放入小顶堆，也就是轮流着给堆插入值，先小后大
            if len(self.maxNums)>0 and num<self.maxNums[0]:
                self.maxHeapInsert(num)
                num = self.maxHeapPop()
            self.minHeapInsert(num)
        
        else: #总长度为奇数，将小顶堆最小数放入大顶堆
            if len(self.minNums)>0 and num>self.minNums[0]:
                self.minHeapInsert(num)
                num = self.minHeapPop()
            self.maxHeapInsert(num)
            
    def GetMedian(self):
        alllen = len(self.minNums)+len(self.maxNums)
        if alllen == 0:
            return -1
        if alllen & 1 == 1: # 总长度为奇数，小顶堆数量多1
            return self.minNums[0]
        else: # 总长度为偶数
            return (self.minNums[0]+self.maxNums[0])/2.0