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.
