Median

class Median {
  MaxHeap maxHeap;
  MinHeap minHeap;
  
  // maintain invariant size of maxHeap equals to or greater than size of minHeap by 1
  public void add(int x) {
    maxHeap.add(x);
    if (maxHeap.size() > minHeap.size() + 1) {
      minHeap.add(maxHeap.remove());
    }
  }
  
  public int getMedian() {
    if ((maxHeap.size() + minHeap.size()) % 2 == 0) {
      return (maxHeap.peek() + minHeap.peek()) / 2;
    } else {
      return maxHeap.peek();
    }
  }
}