codekofi
← All questions

Find Median from Data Stream

HardHeap / Priority Queue

The problem

Values arrive one at a time. After each arrival, report the median of everything seen so far — the middle value when the count is odd, the average of the two middle values when it is even.

Sorting the history after every arrival is not the intended answer.

runMedianFinder({1, 2, 3})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1vector<double> runMedianFinder(const vector<int>& arriving) {
2
3 priority_queue<int> low;
4 priority_queue<int, vector<int>, greater<int>> high;
5 vector<double> ans;
6
7 for (int x : arriving) {
8
9 low.push(x);
10 high.push(low.top());
11
12 if (high.size() >= low.size()) {
13 low.push(high.top());
14 high.pop();
15 }
16
17 if (low.size() > high.size()) {
18 ans.push_back(low.top());
19 } else {
20 double middle = (low.top() + high.top()) / 2.0;
21 ans.push_back(middle);
22 }
23 }
24
25 return ans;
26}
1vector<double> runMedianFinder(const vector<int>& arriving) {
2
3 priority_queue<int> low;
4 priority_queue<int, vector<int>, greater<int>> high;
5 vector<double> ans;
6
7 for (int x : arriving) {
8
9 low.push(x);
10 high.push(low.top());
11 low.pop();
12
13 if (high.size() > low.size()) {
14 low.push(high.top());
15 high.pop();
16 }
17
18 if (low.size() > high.size()) {
19 ans.push_back(low.top());
20 } else {
21 double middle = (low.top() + high.top()) / 2.0;
22 ans.push_back(middle);
23 }
24 }
25
26 return ans;
27}
1vector<double> runMedianFinder(const vector<int>& arriving) {
2
3 priority_queue<int> low;
4 priority_queue<int, vector<int>, greater<int>> high;
5 vector<double> ans;
6
7 for (int x : arriving) {
8
9 low.push(x);
10 high.push(low.top());
11
12 if (!(high.size() > low.size())) {
13 low.push(high.top());
14 high.pop();
15 }
16
17 if (low.size() > high.size()) {
18 ans.push_back(low.top());
19 } else {
20 double middle = (low.top() + high.top()) / 2.0;
21 ans.push_back(middle);
22 }
23 }
24
25 return ans;
26}