streaming-median
12345678910111213141516171819202122232425262728293031
#include <bits/stdc++.h>
using namespace std;
int main() {
priority_queue<int> maxHeap;
priority_queue< int, vector<int>, greater<int> > minHeap;
int i = 1, size = 11;
while (i < size) {
if (!maxHeap.empty() && i > maxHeap.top()) {
minHeap.push(i);
} else {
maxHeap.push(i);
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top()); maxHeap.pop();
} else if (minHeap.size() > maxHeap.size() + 1) {
maxHeap.push(minHeap.top()); minHeap.pop();
}
if (maxHeap.size() == minHeap.size()) {
cout << ((maxHeap.top() + minHeap.top()) / 2.0) << endl;
} else {
cout << (maxHeap.size() > minHeap.size() ? maxHeap.top() : minHeap.top()) << endl;
}
i++;
}
return 0;
}
Cpp
INFO