@Ashish: The idea is to keep two heaps, a max-heap of the smallest half of the elements and a min-heap of the largest elements. You insert incoming elements into the appropriate heap. If the result is that the number of elements in the two heaps differs by more than 1, then you move the top element from the longer heap into the other one, thereby equalzing the number of elements. Thus, inserting an element is an O(log n) operation. To get the median, it is the top element of the longer heap, or, if the heaps are of equal length, it is the average of the two top elements. This is O(1).
Dave On May 14, 8:34 am, Ashish Goel <ashg...@gmail.com> wrote: > not clear, can u elaborate.. > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal <agr.bhav...@gmail.com>wrote: > > > > > This problem can be solved using 2 heaps and the median can always be > > accessed in O(1) time ,the first node. > > > -- > > 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.- Hide quoted text - > > - Show quoted text - -- 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.
