# C++ two heaps solution

• ``````class MedianFinder {
private:
priority_queue<int, vector<int>, greater<int>> min_heap;
priority_queue<int, vector<int>, less<int>> max_heap;
public:

// Adds a number into the data structure.
if (min_heap.empty() || (num >= min_heap.top())) {
min_heap.emplace(num);
} else {
max_heap.emplace(num);
}

if (min_heap.size() > max_heap.size() + 1) {
max_heap.emplace(min_heap.top());
min_heap.pop();
} else if (max_heap.size() > min_heap.size()) {
min_heap.emplace(max_heap.top());
max_heap.pop();
}
}

// Returns the median of current data stream
double findMedian() {
return min_heap.size() == max_heap.size()
? 0.5 * (min_heap.top() + max_heap.top())
:  min_heap.top();
}
};``````

• Would be great if you could provide a worded explanation of what this does. Say, maintains the invariant that there are the same number of elements in the `min_heap` as there are in the `max_heap`. (With the caveat that the `min_heap` is allowed at most one number more.)

• There are two conditions.
1): If the total number is even, then get the top of min_heap and max_heap to get the median. 2): If the total number is odd, always keep the median on min_heap. You can also keep it on the max_heap. It's your own decision.

• just a question, how to limit the size of the heap?
Since if we have a huge stream, it will become more and more slow when adding a new number.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.