题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

就是把数组分成两部分（左，中位数，右）
左维持着大根堆，右边维持着小根堆
先把数字放进右边的堆，当两边堆的规模相差>1，则把右边的堆顶放到左边的小根堆

如果总的插入个数是奇数，那么就是右边的堆顶，偶数就是 左右堆顶//2

存复数是因为heapq不太支持大根堆，所以对存大根堆的时候，对每个元素取负，按照小根堆来存，结果一模一样

# -*- coding:utf-8 -*-
# 数据流的意思数字一个一个传参进来，所以根据中位数，把数据流分成（左，中，右）
import heapqclass Solution:def __init__(self):self.max_heap = []self.min_heap = []self.count = 0def Insert(self, num):# write code hereself.count += 1heapq.heappush(self.min_heap, num)if abs(len(self.min_heap) - len(self.max_heap)) > 1:ret = heapq.heappop(self.min_heap)heapq.heappush(self.max_heap, -ret)def GetMedian(self):# write code hereret_min_heap = heapq.heappop(self.min_heap)ret_max_heap = -heapq.heappop(self.max_heap)if self.count % 2 == 0:return (ret_max_heap + ret_min_heap) // 2else:return ret_min_heaps = Solution()
a = [5,2,3,4,1,6,7,0]
for i in a:s.Insert(i)
print(s.GetMedian())
a.sort()
print(a)