MedianStream; Part 2

MedianStream_solution.cc

class MedianStream {
 public:
  // Constructor
  MedianStream() {
    numValues = 0;
  }
  
  // Adds integer value to the stream
  void addNumber(int x) {
    numValues++;
    
    // The algorithm described above
    if (!leftHalf.empty() && x > leftHalf.top()) {
      rightHalf.push(x);
    } else {
      leftHalf.push(x);
    }
    
    if (rightHalf.size() > leftHalf.size()) {
      leftHalf.push(rightHalf.top());
      rightHalf.pop();
    }
    
    if (leftHalf.size() > rightHalf.size() + 1) {
      rightHalf.push(leftHalf.top());
      leftHalf.pop();
    }
  }
  
  // Returns median of all numbers seen so far
  // Assuming this function is not called on empty lists
  double getMedian() {
    // Handling cases for odd and even numValues
    if (numValues % 2 == 0) {
      return (leftHalf.top() + rightHalf.top())/2.0;
    } else {
      return leftHalf.top();
    }
  }

 private:
  int numValues;
  // This is a max-heap in C++:
  priority_queue<int> leftHalf;
  // This is a min-heap in C++:
  priority_queue<int, vector<int>, greater<int>> rightHalf;
};