@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 <thebossku...@gmail.com> 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 <sangeeta15...@gmail.com> 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 algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.