@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected] > > >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 [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.-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 [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.- 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 [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.
