-
Notifications
You must be signed in to change notification settings - Fork 3
/
Find Median from Data Stream
29 lines (27 loc) · 1 KB
/
Find Median from Data Stream
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MedianFinder {
private:
priority_queue<int> firstQ; // max_heap for the first half
priority_queue<int, std::vector<int>, std::greater<int> > secQ; // min_heap for the second half
public:
// Adds a number into the data structure.
void addNum(int num) {
if(firstQ.empty() || (firstQ.top()>num)) firstQ.push(num); // if it belongs to the smaller half
else secQ.push(num);
// rebalance the two halfs to make sure the length difference is no larger than 1
if(firstQ.size() > (secQ.size()+1))
{
secQ.push(firstQ.top());
firstQ.pop();
}
else if(firstQ.size()+1<secQ.size())
{
firstQ.push(secQ.top());
secQ.pop();
}
}
// Returns the median of current data stream
double findMedian() {
if(firstQ.size() == secQ.size()) return firstQ.empty()?0:( (firstQ.top()+secQ.top())/2.0);
else return (firstQ.size() > secQ.size())? firstQ.top():secQ.top();
}
};