Srinath.Venigandla
BAN USEROk guys,all problems resolved,I think i finally found out what Abhi actually meant...
Basically there are two heaps and one integer holding the median value..
if data> median
insert into minheap
else
insert into maxheap
if abs(sizediff)>1
adjust such that an element from the higher sized heap is popped into the median variable and erstwhile median is pushed onto the other heap thus balancing the heaps...
The actual median can be gotten using the tops of heaps plus the median variable because we may need to average if the total size is even.
Here's the actual code...
int median()
{
int median;
fin.open("inp.txt");
M=new MinHeap();
N=new MaxHeap();
int temp,sizediff;
fin>>temp;
median=temp;
while(!fin.eof())
{
fin>>temp;
if(temp>=median)
M.insert(temp);
else if(temp<median)
N.insert(temp);
sizediff=M.size()-N.size();
if(sizediff>1)
{
temp=median;
median=M.pop();
N.insert(temp);
}
else if(sizediff<-1)
{
temp=median;
median=N.pop();
M.insert(temp);
}
}
sizediff=M.size()-N.size();
if(sizediff==1)
return (M.top()+median)/2;
else if(sizediff==-1)
return (N.top()+median)/2;
else if(sizediff==0)
return median;
}
This is much better than the two heap approach,I am not even sure whether the heap approach can actually work...An upgrade to this algorithm would be to try to split till we get a partition of size at most 10^7,also while writing to a file we could keep track of max and min and divide intervals based on those instead of random sampling.
- Srinath.Venigandla April 27, 2013After we get a partition of about 10^7 we could use the ith order statistic method(similar to quicksort) to get the median in O(n) time instead of sorting the elements and taking O(NlogN) time..
But with infinite input i dont think it is possible to retrieve the median in O(1) time at any given time..