@Arun.. If the no. of elements are odd then the median would be the middle element... But, diff would be 0.
In case of even elements diff is either -1 or 1. To prove the above, Say currently diff is -1. and say maxH has X elements. That means minH has X+1 elements. Hence the total no. of elements sent by the stream would be X + (X+1) + (current median) = Even no. of elements. Therefore 2 elements need to be picked. On Dec 26, 9:42 pm, Arun Vishwanathan <[email protected]> wrote: > @lucifer: can you explain to me in the current median calculation why if > there is a Diff =1 or -1 you are using M and top(maxh) or M and top(minh) > for median calculation. If the number of elements from the stream so far is > odd then median is just one element and not average of 2 elements right? > > > > > > > > > > On Fri, Dec 16, 2011 at 2:06 AM, Lucifer <[email protected]> wrote: > > @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. > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily." -- 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.
