题解 | #数据流中的中位数# #堆排序 #python

1.维护两个堆：一个大顶堆放在左边：left，一个小顶堆放在右边：right。

2.每次新进数据的时候更新一下堆，保持两个堆数量动态平衡。

3.每次取中间数的时候，看两个堆的总数量，如果是奇数：那么取大顶堆的根，这个数字是左边最大的。如果是偶数，那么取两个堆的根的平均数，因为大顶堆是左边最大的，小顶堆是右边最小的。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.left = []  # 大顶堆
        self.right = []  # 小顶堆
        self.count = 0

    def Insert(self, num):
        # write code here
        if self.count % 2 == 1:
            # 1.如果是已经添加奇数个，那么往右边添加数字：
            # 放到右边：先放进左边大顶堆，然后pop出最大的放到右边
            self.left.append(num)
            n = len(self.left)
            # 更新大顶堆
            for i in range(n//2, -1, -1):
                self.heap_max(i, n)
            self.right.append(self.left.pop(0))
            #  去掉根之后需要再更新大顶堆
            n = len(self.left)
            for i in range(n//2, -1, -1):
                self.heap_max(i, n)
            # 更新小顶堆
            n = len(self.right)
            for i in range(n//2, -1, -1):
                self.heap_min(i, n)
        else:
            # 2.如果已经添加偶数个，那么需要往左边添加数字：
            # 放到左边：需要先放进小顶堆，然后pop出最小的放在左边
            self.right.append(num)
            n = len(self.right)
            # 更新小顶堆
            for i in range(n//2, -1, -1):
                self.heap_min(i, n)
            self.left.append(self.right.pop(0))
            # 去掉根之后需要再更新小顶堆
            n = len(self.right)
            for i in range(n//2, -1, -1):
                self.heap_min(i, n)
            # 更新大顶堆
            n = len(self.left)
            for i in range(n//2, -1, -1):
                self.heap_max(i, n)
        self.count += 1

    def GetMedian(self):
        # write code here
        if self.count % 2 == 1:
            return self.left[0]
        else:
            return (self.left[0] + self.right[0]) / 2.0

    def heap_max(self, i, n):
        j = i * 2 + 1
        while j < n:
            if j + 1 < n and self.left[j + 1] > self.left[j]:
                j += 1
            if self.left[j] > self.left[i]:
                self.left[j], self.left[i] = self.left[i], self.left[j]
                i = j
                j = i * 2 + 1
            else:
                break

    def heap_min(self, i, n):
        j = i * 2 + 1
        while j < n:
            if j + 1 < n and self.right[j + 1] < self.right[j]:
                j += 1
            if self.right[j] < self.right[i]:
                self.right[j], self.right[i] = self.right[i], self.right[j]
                i = j
                j = i * 2 + 1
            else:
                break