Your sliding window should not be small enough to get the median. For a free running stream, your window should be of size not less than 100.
On Sun, May 15, 2011 at 7:35 PM, Akshata Sharma <akshatasharm...@gmail.com>wrote: > @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. > -- 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.
