这要取决于你取中位数的频率如何。

如果你取中位数的频率不高，那么可以把输入放到无序数组中，并且使用" median of medians "算法使每次取中位数的操作达到线性的时间复杂度。这种方法的优点是每次插入的时间是O(1)，并且取中位数的操作还是很快的O(n)。

如果你需要频繁的取中位数（比如每次输入一个数都要得到当前的中位数），那么可以采用两个堆的方案，这可以让每次取中位数的操作达到O(1)，不过每次插入就要相对慢些O(lg n)。该算法的思路是 使用一个max-heap存放所有数字中较小的一半数，使用一个min-heap存放较大的另一半数 。因此在每次插入新数的过程中要维护这样的关系。

1. max-heap的元素个数与min-heap相等，或者比min-heap大1。因此当前总数为偶数2N时，max-heap与min-heap中各有N个元素；当前总数为奇数2N+1时，max-heap有N+1个元素，min-heap有N个元素。
2. max-heap中的所有元素都比min-heap中的元素小。根据堆的性质，即max(max-heap) < min(min-heap)。

满足了上面的两个条件后，当总数为2N时，中位数有两个，max(max-heap)和min(min-heap)；当总数为2N+1时，中位数为max(max-heap)。由堆的性质，这两个操作都是O(1)的。

以下是该算法的python实现，从代码中可以看到insert的时候是如何维护两个堆的关系的。

  class streamMedian:
  

  def __init__(self):
  

  self.minHeap, self.maxHeap = [], []
  

  self.N=0
  

  

  def insert(self, num):
  

  if self.N%2==0:
  

  heapq.heappush(self.maxHeap, -1*num)
  

  self.N+=1
  

  if len(self.minHeap)==0:
  

  return
  

  if -1*self.maxHeap[0]>self.minHeap[0]:
  

  toMin=-1*heapq.heappop(self.maxHeap)
  

  toMax=heapq.heappop(self.minHeap)
  

  heapq.heappush(self.maxHeap, -1*toMax)
  

  heapq.heappush(self.minHeap, toMin)
  

  else:
  

  toMin=-1*heapq.heappushpop(self.maxHeap, -1*num)
  

  heapq.heappush(self.minHeap, toMin)
  

  self.N+=1
  

  

  def getMedian(self):
  

  if self.N%2==0:
  

  return (-1*self.maxHeap[0]+self.minHeap[0])/2.0
  

  else:
  

  return -1*self.maxHeap[0]
 

注： heapq是python的min-heap实现，这里在插入的时候把每个数都变成负的，从而达到用min-heap模拟max-heap的目的。