# Median of running stream in O(nlog(n)) time complexity? A++

• ``````#include<iostream>

using namespace std;
int sizM=0, sizN=0 ;
int M[500], N[500];

void  MaxHeapify(int i)
{
if(i>=sizM) return;
int curr=i;
int l=i*2+1;
int r=i*2+2;

if(l<sizM && M[curr]<M[l])
curr=l;
if(r<sizM && M[curr]<M[r])
curr=r;

if(curr!=i)
{   swap(M[curr],M[i]);
MaxHeapify(curr);
}
}
void  MinHeapify(int i)
{

if(i>=sizN) return;
int curr=i;//3542
int l=i*2+1;
int r=i*2+2;

if(l<sizN && N[curr]>N[l])
curr=l;
if(r<sizN && N[curr]>N[r])
curr=r;

if(curr!=i)
{   swap(N[curr],N[i]);
MinHeapify(curr);
}
}

void  MaxHeapifyBU(int i)
{

int parent=(i-1)/2;
int t=parent;
int l=parent*2+1;
int r=parent*2+2;

if(l<sizM && M[parent]<M[l])
parent=l;
if(r<sizM && M[parent]<M[r])
parent=r;

if(parent!=(i-1)/2)
{   swap(M[parent],M[t]);
MaxHeapifyBU(t);
}

}

void  MinHeapifyBU(int i)
{

int parent=(i-1)/2;
int t=parent;
int l=parent*2+1;
int r=parent*2+2;

if(l<sizN && N[parent]>N[l])
parent=l;
if(r<sizN && N[parent]>N[r])
parent=r;

if(t!=parent)
{
swap(N[parent],N[t]);
MinHeapifyBU(t);
}
}
void  Maxinsert(int key)
{

sizM++;
M[sizM-1]=key;

MaxHeapifyBU(sizM-1);
}
void Mininsert(int key)
{

sizN++;
N[sizN-1]=key;

MinHeapifyBU(sizN-1);
}

int  NeedHelp(int key)
{

if(sizM==0)
{
Maxinsert(key);
return M[0];
}
if(sizN==0)
{
Mininsert(key);
return (M[0]+N[0])/2;
}
if(key<M[0])
{
swap(M[0],key);        //key should be in middle of M[0] and N[0]...
MaxHeapify(0);
}
else
if(key>N[0])
{
swap(N[0],key);        //key should be in middle of M[0] and N[0]...
MinHeapify(0);
}

if(sizM>sizN)
Mininsert(key);
else
Maxinsert(key);

if(sizM==sizN)
return (M[0]+N[0])/2;
else
return sizM>sizN?M[0]:N[0];         //@IIT BHU @omp3010
}

int main()
{

int a[]={5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4};

int n=sizeof(a)/sizeof(a[0]);

for(int i=0 ;i<n ;i++)
cout<<NeedHelp(a[i])<<endl;

return 0;
}``````

• This post is deleted!

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.