@ Dave. Nice explanation On Fri, May 20, 2011 at 6:06 AM, saurabh agrawal <saurabh...@gmail.com>wrote:
> Thanks Dave. > > On Wed, May 18, 2011 at 8:01 PM, Dave <dave_and_da...@juno.com> wrote: > >> @Saurabh: You look at the top elements in the two heaps. If the new >> number is between the values of the top of the heaps, you add it to >> the shorter of the two heaps, or to either heap if they are of equal >> length. If the new number is larger than the min of the min-heap, you >> add it to the min-heap. If it is smaller than the max of the max-heap, >> you add it to the max heap. If the resulting two heaps differ in >> length by more than one element, you move the top element from the >> longer heap into the shorter heap. Since the heaps start off empty and >> you add only one number at a time, the result of a step of the >> algorithm is that the two heaps will differ in size by at most one >> element. Thus, the smaller half of the numbers will be in the max-heap >> and the larger half will be in the min-heap. >> >> Dave >> >> On May 18, 8:29 am, saurabh agrawal <saurabh...@gmail.com> wrote: >> > Dave, >> > u said:" a max-heap of the smallest >> > half of the elements" >> > but if the number are randomply generated, then how will you get to know >> > whether a number belongs to smallest half OR lager half.. >> > i didnt got it... >> > >> > >> > >> > On Sat, May 14, 2011 at 9:10 PM, Dave <dave_and_da...@juno.com> wrote: >> > > @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.- 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. >> >> > -- > 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. > -- 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.
