On Sat, May 14, 2011 at 12:55 PM, 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.
>
You cannot do it with a vanilla balanced binary tree.
But you can, if you use an augmented tree in the following sense - In
each node of the tree, store the number of nodes in the subtree rooted
at that node.
So , for eg,
- the root node will store N where N is the total number of nodes in the tree,
- number stored in left child of root + number stored in right child
of root = N - 1
Then, to find the element appearing at the N/2th position in an
inorder walk (i.e. the median) is given by Find(root, N/2) where Find
is defined like so -
Node* Find(Node* ptr, int position)
{
int ptrpos = ptr->left->numchildren + 1;
if(ptrpos == position) return ptr;
else if(ptrpos >position) return Find(ptr->left, position);
else return Find(ptr->right, position - ptrpos);
}
> 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.
>
> --
> 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.
