41. 数据流中的中位数

利用两个堆：

1. 用于存储输入数字中较小一半的最大堆（最大堆中的所有数字都小于或等于最大堆的top元素）
2. 用于存储输入数字的较大一半的最小堆（最小堆中的所有数字都大于或等于最小堆的顶部元素）

只要这两个堆是平衡的（即这两个堆的数量相等或相差1），那么中位数就可以通过这两个堆的堆顶元素获得
具体解释可以参考leetcodehttps://leetcode-cn.com/problems/find-median-from-data-stream/solution/you-xian-dui-lie-python-dai-ma-java-dai-ma-by-liwe/

import heapq
class Solution:
    def __init__(self):
        self.count = 0
        self.max_heap = []
        self.min_heap = []

    def Insert(self, num):
        # write code here
        self.count += 1
        #将数据放到最大堆中
        heapq.heappush(self.max_heap, -num)
        #将最大堆中的堆顶元素放到最小堆中
        max_heap_top = heapq.heappop(self.max_heap)
        heapq.heappush(self.min_heap, -max_heap_top)
        #如果最小堆和最大堆之间的差距大于1，将最小堆中的堆顶放进最大堆
        if self.count & 1:
            min_heap_top = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -min_heap_top)

    #题目getmedian参数少了个s       
    def GetMedian(self,s):
        # write code here
        if self.count & 1:
            return -self.max_heap[0]
        else:
            return (self.min_heap[0] - self.max_heap[0]) / 2.0