python 代码

class Solution:

    # 定义一个初始化方法
    def __init__(self):
        # 创建 两个数组 表示 最大堆(存放较大元素) 和 最小堆中的元素(存放较大元素)
        self.smallValueMaxHeap = []
        self.bigValueMinHeap = []

        # 创建两个变量 分别 记录 最大堆 和 最小堆中元素的个数
        self.maxHeapCount = 0
        self.minHeapCount = 0


    def insert(self, num):
        # 判断 最大堆 和 最小堆中的元素的数量
        # 如果 最大堆中的元素 高于 最小堆中元素的数量 那么执行最小堆中插入元素
        if self.minHeapCount < self.maxHeapCount:
            # 最小堆中元素的数量 + 1
            self.minHeapCount += 1
            # 第一种情况 插入的值是 最大堆中 剔除掉的
            if num < self.smallValueMaxHeap[0]:

                # 首先 将 最大堆的 原始堆顶元素 保存
                tempValue = self.smallValueMaxHeap[0]

                # 然后 执行 最大堆的调整过程
                self.adjustMaxHeap(num)

                # 然后 执行 最小堆中插入元素
                self.createMinHeap(tempValue)

            # 如果 这个值 大于 最大堆的堆顶元素 那么不会 最大堆不会调整
            # 直接添加元素到 最小堆中
            else:
                self.createMinHeap(num)


        # 如果 两个堆中元素 个数相同 那么 在最大堆中 插入元素
        else:
            # 如果 最大堆是空 那么 最小堆中元素 肯定也是空 不需要去 最小堆中比较调整了
            if self.maxHeapCount == 0:
                # 直接 插入
                self.createMaxHeap(num)
                self.maxHeapCount += 1


            else:
                self.maxHeapCount += 1
                # 如果 这个值的 大于 最小堆的 堆顶元素 那么 最大堆中插入的元素就是
                # 最小堆中 提出的元素
                if num > self.bigValueMinHeap[0]:

                    # 保存 最小堆中提出的原始的最堆顶元素
                    tempValue = self.bigValueMinHeap[0]

                    # 调整 最小堆
                    self.adjustMinHeap(num)

                    # 最大堆中插入元素
                    self.createMaxHeap(tempValue)

                else:
                    # 如果 这个值 小于 最小堆的 堆顶元素 那么直接插入到 最大堆 就可以了
                    self.createMaxHeap(num)



    def getMedian(self):
        # 如果 最大堆的元素 大于 最小堆的元素个数 那么 一共 奇数个元素
        # 返回 最大堆的 堆顶元素
        if self.maxHeapCount > self.minHeapCount:
            return self.smallValueMaxHeap[0]

        # 如果相等 那么 返回 两个堆的 堆顶元素的和 的 平均值 
        else:
            # 因为 字节流中的数 可能是 浮点数 因此 使用 float进行类型转化
            return float(self.smallValueMaxHeap[0] + self.bigValueMinHeap[0]) / 2



    # 定义一个方法 表示 创建（插入）最大堆的过程
    def createMaxHeap(self, num):
        # 首先 添加数据到 最大堆中
        self.smallValueMaxHeap.append(num)
        # 当前位置的 索引(从后面插入~)
        currentIndex = self.maxHeapCount - 1

        # 不断地向上 和 父节点比较 如果当前节点的值 大于 父节点的值
        # 那么交换两者的位置(最大堆 上面的元素比较大)
        # 之后 继续向上比较 直到索引为0即到了父节点 或 
        # 出现了 某个父节点 高于 当前节点的值(上面都是最大堆的结构) 停止循环
        while currentIndex:
            # 当前节点 父节点的索引
            parentIndex = (currentIndex - 1) // 2

            if self.smallValueMaxHeap[parentIndex] < self.smallValueMaxHeap[currentIndex]:
                # exchange position
                self.smallValueMaxHeap[parentIndex], self.smallValueMaxHeap[currentIndex] = \
                self.smallValueMaxHeap[currentIndex], self.smallValueMaxHeap[parentIndex]

                # 当前索引 变为 上一个父节点的索引
                currentIndex = parentIndex
            # 出现了 某个父节点 高于 当前节点的值(上面都是最大堆的结构) 停止循环 
            else:
                break


    # 定义一个方法 表示 调整 最大堆的过程(当前的值 和 堆顶元素的值进行比较)
    def adjustMaxHeap(self, num):
        # 这个方法 能执行下去的条件是 当前的num值 小于 堆顶元素的值
        # 那么 堆顶元素滚蛋(滚到最小堆那边) 并用这个num值 作为 堆顶元素的值
        if num < self.smallValueMaxHeap[0]:

            self.smallValueMaxHeap[0] = num

            # 当前索引(开始在 堆顶)
            currentIndex = 0

            # 接下来就是调整的过程 不断的和 下一层中的最大值 进行比较
            # 如果 当前的节点的值 小于 下一层中的最大值 那么交换位置
            # 并 继续 和下一层进行比较
            while currentIndex < self.maxHeapCount:

                '''首先获取 下一层的最大值'''
                # 左右节点的索引
                leftIndex = currentIndex * 2 + 1
                rightIndex = currentIndex * 2 + 2

                # 因为两个值 因此用 比较级
                largerIndex = 0

                # 如果 两个子节点 的下标 都没越界
                if rightIndex < self.maxHeapCount:
                    # 获取较大的值的 索引
                    if self.smallValueMaxHeap[leftIndex] < self.smallValueMaxHeap[rightIndex]:

                        largerIndex = rightIndex

                    else:

                        largerIndex = leftIndex

                # 如果 右节点索引越界(None) 左子节点没越界
                elif leftIndex < self.maxHeapCount:
                        largerIndex = leftIndex

                # 如果都越界 向下比较结束
                else:
                    break


                # 上面的操作获得了 下一层中 最大值
                # 当前值 和 其进行比较
                if self.smallValueMaxHeap[currentIndex] < self.smallValueMaxHeap[largerIndex]:
                    # exchange position
                    self.smallValueMaxHeap[currentIndex], self.smallValueMaxHeap[largerIndex] = \
                    self.smallValueMaxHeap[largerIndex], self.smallValueMaxHeap[currentIndex] 

                    # 当前索引 向下移动
                    currentIndex = largerIndex

                # 如果当前的 节点值 大于u下一层的最大值 那么 停止循环 因此 下面都是 最大堆的结构    
                else:
                    break


    # 定义一个方法 表示 创建（插入）最小堆的过程
    def createMinHeap(self, num):
        # 首先 添加数据到 最小堆中
        self.bigValueMinHeap.append(num)
        # 当前位置的 索引(从后面插入~)
        currentIndex = self.minHeapCount - 1

        # 不断地向上 和 父节点比较 如果当前节点的值 小于 父节点的值
        # 那么交换两者的位置(最小堆 上面的元素比较小)
        # 之后 继续向上比较 直到索引为0即到了父节点 或 
        # 出现了 某个父节点 小于 当前节点的值(上面都是最小堆的结构) 停止循环
        while currentIndex:
            # 当前节点 父节点的索引
            parentIndex = (currentIndex - 1) // 2

            if self.bigValueMinHeap[currentIndex] < self.bigValueMinHeap[parentIndex]:
                # exchange position
                self.bigValueMinHeap[parentIndex], self.bigValueMinHeap[currentIndex] = \
                self.bigValueMinHeap[currentIndex], self.bigValueMinHeap[parentIndex]

                # 当前索引 变为 上一个父节点的索引
                currentIndex = parentIndex
            # 出现了 某个父节点 高于 当前节点的值(上面都是最小堆的结构) 停止循环 
            else:
                break


    # 定义一个方法 表示 调整 最小堆的过程(当前的值 和 堆顶元素的值进行比较)
    def adjustMinHeap(self, num):
        # 这个方法 能执行下去的条件是 当前的num值 大于 堆顶元素的值
        # 那么 堆顶元素滚蛋(滚到最大堆那边) 并用这个num值 作为 堆顶元素的值
        if num > self.bigValueMinHeap[0]:

            self.bigValueMinHeap[0] = num

            # 当前索引(开始在 堆顶)
            currentIndex = 0

            # 接下来就是调整的过程 不断的和 下一层中的最小值 进行比较
            # 如果 当前的节点的值 大于 下一层中的最小值 那么交换位置
            # 并 继续 和下一层进行比较
            while currentIndex < self.minHeapCount:

                '''首先获取 下一层的最小值'''
                # 左右节点的索引
                leftIndex = currentIndex * 2 + 1
                rightIndex = currentIndex * 2 + 2

                # 因为两个值 因此用 比较级
                smallerIndex = 0

                # 如果 两个子节点 的下标 都没越界
                if rightIndex < self.minHeapCount:
                    # 获取较大的值的 索引
                    if self.bigValueMinHeap[leftIndex] < self.bigValueMinHeap[rightIndex]:

                        smallerIndex = leftIndex

                    else:

                        smallerIndex = rightIndex

                # 如果 右节点索引越界(None) 左子节点没越界
                elif leftIndex < self.minHeapCount:
                        smallerIndex = leftIndex

                # 如果都越界 向下比较结束
                else:
                    break


                # 上面的操作获得了 下一层中 最小值
                # 当前值 和 其进行比较
                if self.bigValueMinHeap[currentIndex] > self.bigValueMinHeap[smallerIndex]:
                    # exchange position
                    self.bigValueMinHeap[currentIndex], self.bigValueMinHeap[smallerIndex] = \
                    self.bigValueMinHeap[smallerIndex], self.bigValueMinHeap[currentIndex] 

                    # 当前索引 向下移动
                    currentIndex = smallerIndex

                # 如果当前的 节点值 小于 下一层的最小值 那么 停止循环 因此 下面都是 最小堆的结构    
                else:
                    break