@Anand: if the stream is let 1,2,3,4,6,7,9 and let we choose k=3
then your algo is giving 7 as the median. On Mon, May 16, 2011 at 4:39 AM, Anand <anandut2...@gmail.com> wrote: > Complexity will be O(logK) to insert, delete and finding the predecessor or > successor of current median value in the BST. > > > On Sun, May 15, 2011 at 4:08 PM, Anand <anandut2...@gmail.com> wrote: > >> 1. Create a BST for first K elements of the running stream. >> 2. Find the median of first K elements. >> 3. With every new element from the stream, Insert the new element in >> Binary search Tree. >> 4. Delete the first element from BST. >> 5. if the new element is greater than the current median value, find the >> successor of current median value. >> 6. else if the new elment is less than the current median value, find the >> predecessor of the currend median value in BST. >> >> >> >> On Sun, May 15, 2011 at 2:51 AM, pacific :-) <pacific4...@gmail.com>wrote: >> >>> 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. >>> >> >> > -- > 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.
