从零开始实现堆，获取数据流中的中位数。中位数可能由两位数决定，所以需要两个堆。
中位数特点：对于排好序的序列，它是左半部分的最大值，是右半部分的最小值。当元素个数是偶数时，左右半部分元素个数相等，中位数是左边最大和右边最小的平均，当元素个数是奇数时，让左半部分多一个元素，那么中位数就是左半部分的最大值。
那么左边维护一个大根堆，右边维护一个小根堆，并且维护大根堆的堆顶元素不大于小根堆的堆顶元素。
接收到第奇数个数据，插入大根堆，接收到第偶数个数，插入小根堆。 
# 中位数特点，左边的最大值，右边的最小值
# 维护两个堆，一个大根堆，一个小根堆，要求大根堆堆顶元素小于等于小根堆堆顶元素
class Solution:
    def __init__(self):
        self.left = []    # 数据流排序后左半部分
        self.right = []   # 数据流排序后右半部分
    # 大根堆调整函数
    @staticmethod
    def heapAdjust(lis, i, end):
        j = 2*i + 1
        while j < end:
            if j+1 < end and lis[j+1] > lis[j]:
                j += 1
            if lis[j] > lis[i]:
                lis[i], lis[j] = lis[j], lis[i]
                i = j
                j = 2*i + 1
            else:
                break
    # 大根堆插入函数
    @staticmethod
    def heappush(lis, num):
        # 尾插
        lis.append(num)
        j = len(lis) - 1 # 插入节点的下标
        # 调整堆
        while j > 0:
            i = (j-1)//2 # 定位父节点下标
            if lis[i] < lis[j]: # 父小于子，交换
                lis[i], lis[j] = lis[j], lis[i]
                j = i
            else:
                break
    
    def heappop(self, lis):
        lis[0], lis[-1] = lis[-1], lis[0]
        pop = lis.pop()
        self.heapAdjust(lis, 0, len(lis)-1)
        return pop
    def Insert(self, num):
        # 保证右边的值比左边大，奇数个数填左，保证奇数时左边多一个
        # 当前接收到数据个数总数为奇数，左边加值，但是加的值必须不大于右边最小值（堆顶）。
        # 如果接收到的数据不满足条件，则与右边最小值交换，再各自插入。
        if len(self.left) == len(self.right):  # 原先左右相等，当前是奇数个
            if not self.left:
                self.heappush(self.left, num)
            elif num > -self.right[0]:
                self.heappush(self.left, -self.heappop(self.right))
                self.heappush(self.right, -num)
            else:
                self.heappush(self.left, num)
        # 当前接收到数据个数总数为偶数，右边加值，但是加的值必须不小于左边的最大值（堆顶）。
        # 如果接收到的数据不满足条件，则与左边最大值交换，再各自插入。
        else:
            if num < self.left[0]:
                self.heappush(self.right, -self.heappop(self.left))
                self.heappush(self.left, num)
            else:
                self.heappush(self.right, -num)
    def GetMedian(self):
        # 插入完成后self.odd被改变，所以这里not self.odd 表示接收到数据个数为奇数
        return self.left[0] if len(self.left)!=len(self.right) else (self.left[0] -self.right[0])/2