Find Median from Data Stream LeetCode solution in C++

1
class MedianFinder {
2
 public:
3
  /* Implemented @StefanPochmann's Incridible Idea */
4
  priority_queue<long long> small, large;
5
  MedianFinder() {}
6

7
  void addNum(int num) {
8
    small.push(num); // cool three step trick
9
    large.push(-small.top());
10
    small.pop();
11
    while (small.size() < large.size()) {
12
      small.push(-large.top());
13
      large.pop();
14
    }
15
  }
16

17
  double findMedian() {
18
    return small.size() > large.size() ? small.top() : (small.top() - large.top()) / 2.0;
19
  }
20
};