@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.
