思路1：最大堆和最小堆

import heapq#heapq是最小堆操作，取反来模拟最大堆

class Solution:
    def __init__(self):
        self.minHeap=[]
        self.maxHeap=[]

    def insert(self, num):
        """
        :type num: int
        :rtype: void
        """
        heapq.heappush(self.maxHeap,-num)#新的数先一律加到最大堆中去
        if len(self.minHeap) and -self.maxHeap[0]>self.minHeap[0]:#如果最小堆存在，且两个堆顶元素逆序了
            minH,maxH=self.minHeap[0],self.maxHeap[0]
            heapq.heapreplace(self.maxHeap, -minH)#交换两个堆顶元素
            heapq.heapreplace(self.minHeap, -maxH)
        if len(self.maxHeap)>len(self.minHeap)+1:#如果最大堆的元素多了，就放到最小堆去保持两个堆数量平衡
            heapq.heappush(self.minHeap,-self.maxHeap[0])
            heapq.heappop(self.maxHeap)

    def getMedian(self):
        """
        :rtype: float
        """
        if (len(self.maxHeap)+len(self.minHeap))%2!=0:#如果整个数组个数为奇数，则返回最大堆的堆顶
            return -self.maxHeap[0]
        else:
            return (-self.maxHeap[0]+self.minHeap[0])/2.0#否则为两个堆顶的平均值

思路二：用二分往有序数组插一个数

from bisect import bisect
class Solution:
    def __init__(self):
        self.nums = []

    def insert(self, num):
        """
        :type num: int
        :rtype: void
        """
        self.nums.insert(bisect(self.nums, num), num)

    def getMedian(self):
        """
        :rtype: float
        """
        m = len(self.nums) // 2
        return (self.nums[m] + self.nums[m - 1]) / 2 if len(self.nums) % 2 == 0 else self.nums[m]