@sangeeta
I think your question is, given an input stream of nos., at any random
time, we need to find what's the current median.
For eg- say 4 nos have been read till now, hence, whats the median in
those 4 nos. Say now, 7 nos have been read till now from the stream so
which is the current median.. Am i ryt?
If my above understanding is correct.. then the following approach
might work..
Take a variable to store the actual median, say M.
Take 2 heaps, one min-heap and one max heap say, minH and maxH.
Take a variable to store the difference in the no. of elements stored
by both the heaps i.e { count(maxH) - count(minH) }
We need to maintain the following constraint :-
The size of minH and maxH shouldn't differ by more than one.
Say, currently the no. of elements scanned is odd hence, the storage
state will be as follows:
1) sizeof minH = size of maxH
2) M will give u the median.
Say, currently the no. of elements scanned is even hence, the storage
state will be as follows:
1) abs(sizeof maxH - size of minH) = 1
2) M will give u the median.
3) Ideally there are 2 median elements in this case, hence to get the
second median get the top element of the heap which has more no. of
elements.
i.e If sizeof minH > sizeof maxH, then top(minH) is the other median,
apart from M, else top(maxH) is the other median.
Algorithm :
Say, the difference of the size of the heaps is stored in variable,
"Diff" = size(maxH) - size(minH)
// "Diff" can have values -1, 0, 1..
0-> size(minH) = size(maxH),
-1 -> size(minH) = size(maxH) + 1
1 -> size(maxH) = size(minH) + 1
Get the no. from the stream, say X...
a) If M is empty then put M = X;
b) Else,
If (Diff == 0)
{
If (M<= X)
Add X to maxH; Diff = 1;
else
Add X to minH; Diff = -1;
}
else If (Diff == -1)
{
if (M<=X)
Add X to maxH;
else
{
Add M to maxH;
If (X >= top(minH))
M = X;
else
{
M = top(minH);
top(minH) = X;
heapify for top(minH);
}
}
Diff = 0;
}
else
{
if (X<=M)
Add X to minH;
else
{
Add M to minH;
If (X <= top(maxH))
M = X;
else
{
M = top(maxH);
top(maxH) = X;
heapify for top(maxH);
}
}
Diff = 0;
}
To get the current median:
if (Diff == 0)
Current median = M;
else if (Diff == -1 )
Current median = top(minH) and M;
else
Current median = M and top(maxH);
On Dec 16, 12:50 pm, arvind kumar <[email protected]> wrote:
> Hi,have a look at this,n revert back in case of
> doubts:http://www.cs.cmu.edu/~avrim/451/lectures/lect0903.pdf
>
>
>
>
>
>
>
> On Fri, Dec 16, 2011 at 12:56 PM, Sangeeta <[email protected]> wrote:
> > You are given a stream of numbers which can be positive or negative.
> > You are
> > required to provide an operation FIND MEDIAN..which when invoked
> > should be
> > able return the median of the numbers in stream (in sorted order) in
> > O(1)
> > time.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group
> > athttp://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
