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