Given an input stream of n integers. The task is to insert these numbers into a new stream and find the mean of the stream formed by each insertion of X.
Flow in flow: 5, 15, 1, 3
5 goes to stream -> median 5 (5)
15 goes to stream -> median 10 (5, 15)
1 goes to stream -> median 5 (5, 15, 1)
3 goes to stream -> mean 4 (5, 15, 1, 3)
Make sure that you keep the following points in mind while solving:
1. Store all stream numbers in one stream.
2. Store all medians in the median array and print later.
3. Use the maximum stack and minimum stack to solve this problem, quite easy to understand.
Approach using maximum-stack and minimum-stack.
Max-pile: The root is always greater or equal than its child elements.
Minimum Stack: The root is always less than or equal to its child elements.
1: iterating through each element of the array.
2: Add this element to the maximum stack first.
3: Now bring max-max / route from max-heap and balance / send to min-heap.
4. If the min-heap size increases, the max-heap size means that the min-heap is not balanced with the MX-heap, so remove the original value of min-heap / min-heap and Add back to max-heap.
5. Now check whether the two piles are the same size or not? If yes, this means that there were even numbers of arrays, so the mean would be the average of the maximum value from the maximum-heap and the minimum value from the minimum-heap.
If both stacks are of different sizes then there are odd numbers. So take the root element of the big stack. This will be the average and store it in the median array.
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
int N;
cin >> N;
priority_queue<int> maxheap;
priority_queue<int,vector<int>,greater<int> > minheap;
int cur;
cin >> cur;
minheap.push(cur);
N--;
double median = cur;
cout << median <<endl;
while(N--){
int cur;
cin>> cur;
if(minheap.size()>maxheap.size())
{
if(cur > minheap.top())
{
int top = minheap.top();
minheap.pop();
maxheap.push(top);
minheap.push(cur);
}
else
{
maxheap.push(cur);
}
median = (maxheap.top()+minheap.top() )/2;
cout << median <<endl; }else if(minheap.size()<maxheap.size()){ if(cur> maxheap.top())
{
minheap.push(cur);
}
else
{
int top = maxheap.top();
maxheap.pop();
minheap.push(top);
maxheap.push(cur);
}
median = (maxheap.top()+minheap.top() )/2;
cout << median <<endl; }else { if(cur> median)
{
minheap.push(cur);
median = minheap.top();
}
else
{
maxheap.push(cur);
median = maxheap.top();
}
cout << median <<endl; } } return 0; }
