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 <[email protected]> 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 :-) <[email protected]>wrote: > >> perfect. >> >> Thanks for the effort in explanation. >> >> >> On Sun, May 15, 2011 at 12:20 AM, Dave <[email protected]> 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 :-)" <[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. >>> >>> >> >> >> -- >> 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 [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. >> > > -- 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.
