@himansu: how can quicksort selecting kth largest element be done in O(n) time ...I think in worst case it takes O(n^2) time .... will u pls explain this.........
On Fri, Sep 9, 2011 at 2:10 AM, Himanshu Neema < [email protected]> wrote: > @Dave: Thanks for pointing that out . > > In that case , if tree is really big and we want to *save memory* : > *Algorithm #1 :* > 1) Convert tree to a linked list ( Right rotation or left rotation ) : > O(n) > 2) Quick Select Kth largest element : Worst case O(n^2) ( when tree was > already a bst + if we chose pivot to be fist node of linked list everytime) > 3) apply second phase of DSW algorithm to recreate the tree. O(n) > Time : O(n^2) > Space: O(1) > Bonus : After fist call tree is perfectly balanced > > If tree is small , we want to *save run time* : > *Algorithm #2 :* > 1) Traverse tree , store elements in array : O(n) > 2) Quick Select Kth largest element : O(n) > Time : O(n) > Space : O(n) > > > > > On Thu, Sep 8, 2011 at 8:58 AM, Dave <[email protected]> wrote: > >> @Himanshu: You apparently are assuming that the data is presented in a >> binary search tree, but the original problem stated that the data is >> presented in an unordered array. You need to account for the >> complexity of forming the bst and how much space it will take. >> >> Dave >> >> On Sep 7, 7:20 pm, Himanshu Neema <[email protected]> >> wrote: >> > Do reverse inorder and count number of nodes visited, Kth visited node >> will >> > be Kth largest. >> > Time : O(n) >> > Space : O(1) >> > >> > On Mon, Sep 5, 2011 at 5:16 PM, bharatkumar bagana < >> > >> > >> > >> > [email protected]> wrote: >> > > @monish: >> > > u'rs is correct , time =O(nlogn) Ok but, the constant behind this prog >> is >> > > very huge .. >> > > for every number coming in , u maintain minheap and maxheap,and also >> if the >> > > sizes are of mismatch , u delete from minheap and add that to max >> heap--- >> > > here deletion--O(logn),addition--O(logn),this occurs on an average for >> > > every 3 elements ... >> > >> > > On Mon, Sep 5, 2011 at 2:08 AM, sachin goyal <[email protected] >> >wrote: >> > >> > >> @anup,@sukran ithink u both are right in case of binary search >> tree... >> > >> we can traverse and then easily find the value... >> > >> but in case of heap first we have to create the heap and accordingly >> apply >> > >> the algo the create min heap..... >> > >> it will be the complex program.... >> > >> so simple is bst just traverse by inorder and compare >> > >> if anyone has simple solution or any other case then plz tell..... >> > >> > >> On Sun, Sep 4, 2011 at 9:56 PM, monish001 <[email protected] >> >wrote: >> > >> > >>> ALGO: >> > >>> 1. For each element 1 to k: >> > >>> insert in into min-heap >> > >>> 2. for each element k+1 to n >> > >>> delete the root of min-heap and insert this item into the min- >> > >>> heap >> > >>> 3. Finally you have a min-heap of k largest numbers and the root is >> > >>> your answer >> > >> > >>> COMPLEXITY: O(n logn) >> > >> > >>> -Monish >> > >> > >>> On Sep 3, 3:03 pm, teja bala <[email protected]> wrote: >> > >>> > //Asked in MS please help me with the coding or Give an algorithm >> > >> > >>> > Write code to return the kth largest element in a tree ...>>> >> function >> > >>> > prototype is int fucnkth(node *root,int k) >> > >> > >>> -- >> > >>> 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. >> > >> > > -- >> > >> > > **Please do not print this e-mail until urgent requirement. Go Green!! >> > > Save Papers <=> Save Trees >> > > *BharatKumar Bagana* >> > > **http://www.google.com/profiles/bagana.bharatkumar< >> http://www.google.com/profiles/bagana.bharatkumar> >> > > * >> > > Mobile +91 8056127652* >> > > <[email protected]> >> > >> > > -- >> > > 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. >> >> > -- > 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. > -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers <=> Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> * Mobile +91 8056127652* <[email protected]> -- 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.
