We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
"for inserting first two elements, insert bigger element in minHeap and smaller in maxHeap".
No need to insert the first 2 elements in this way, just set the median to zero in the beginning and do everything as mentioned inside the loop.
Here is the implementation in c++
vector<double> runningMedian(vector<int> a) {
vector<double> res;
priority_queue<int, vector<int>, greater<int>> minheap;
priority_queue<int> maxheap;
double median = 0;
for (int i=0; i<a.size(); i++) {
if (a[i] <= median) {
maxheap.push(a[i]);
} else {
minheap.push(a[i]);
}
if (minheap.size() > maxheap.size()+1) {
maxheap.push(minheap.top());
minheap.pop();
}
if (maxheap.size() > minheap.size()+1) {
minheap.push(maxheap.top());
maxheap.pop();
}
if (minheap.size() == maxheap.size()) {
median = (maxheap.top() + minheap.top())/2.0;
} else if(minheap.size() > maxheap.size()) {
median = (double)minheap.top();
} else if (minheap.size() < maxheap.size()) {
median = (double)maxheap.top();
}
res.push_back(median);
}
return res;
}
Find the Running Median
You are viewing a single comment's thread. Return to all comments →
"for inserting first two elements, insert bigger element in minHeap and smaller in maxHeap". No need to insert the first 2 elements in this way, just set the median to zero in the beginning and do everything as mentioned inside the loop.
Here is the implementation in c++