perfect. Thanks for the effort in explanation.
On Sun, May 15, 2011 at 12:20 AM, Dave <dave_and_da...@juno.com> wrote: > @Pacific: A balanced binary tree is commonly defined as a binary tree > in which the height of the two subtrees of every node never differ by > more than 1. Thus, there could be more nodes in one subtree than in > the other. E.g., a balanced binary tree with 11 nodes could have 7 > nodes in the left subtree and only 3 nodes in the right subtree. Thus, > the root would not be the median. > > An additional condition is needed: the number of nodes in the left > subtree differs by at most one from the number of nodes in the right > subtree. > > In fact, given that the heap structure is a balanced binary tree > structure with implicit pointers to the left and right subtrees, the > two-heap algorithm I described results in a balanced binary tree > satisfying this additional condition, with an implicit root node equal > to the median. > > Dave > > On May 14, 11:55 am, "pacific :-)" <pacific4...@gmail.com> wrote: > > Will not a balanced binary tree do the job ? if we will pick the root > each > > time for the median. > > > > > > > > > > > > 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. > > > > -- > > regards, > > chinna.- 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. > > -- regards, chinna. -- 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.
