Sure, we can build a heap. But what's the point. Already, an O(n) solution has been identified, using the median of medians algorithm. A heap would be O(n ln k).
Dave On Apr 14, 4:25 am, Ashish Mishra <[email protected]> wrote: > can't we build a min-heap (kinda opposite of max-heap) ?? > > On Wed, Apr 14, 2010 at 8:42 AM, Rohit Saraf > <[email protected]>wrote: > > > > > Not linear in worst case > > > On 4/13/10, souri datta <[email protected]> wrote: > > > what about the algorithm which mimics the Quick Sort and deals with only > > one > > > partition( as in Coremen) ? > > > > On Tue, Apr 13, 2010 at 9:11 AM, Rohit Saraf < > > [email protected]> > > > wrote: > > > >> So tell me something else which works in O(n) > > > >> On 4/12/10, souri datta <[email protected]> wrote: > > >> > Why only median of median? > > > >> > On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf > > >> > <[email protected]> > > >> > wrote: > > > >> >> Find the kth element using order statistics - O(n) <> As far as i > > >> >> know , > > >> >> u will have to use median of medians selection algorithm for this... > > >> >> Rest is fine.. > > > >> >> -------------------------------------------------- > > >> >> Rohit Saraf > > >> >> Second Year Undergraduate, > > >> >> Dept. of Computer Science and Engineering > > >> >> IIT Bombay > > >> >>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > >> >> On Mon, Apr 12, 2010 at 3:20 PM, souri datta < > > [email protected]> > > >> >> wrote: > > > >> >>> Steps: > > >> >>> 1. Find the kth element using order statistics - O(n) > > >> >>> 2. In one pass over the array, get all the elems less than the kth > > >> >>> element. > > > >> >>> Let me know if this is not correct. > > > >> >>> On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf > > >> >>> <[email protected]> wrote: > > > >> >>>> I have already given an O(n) solution. See above ! > > > >> >>>> The BST solution is O(nlogn) but is practically more nice. :) > > > >> >>>> -------------------------------------------------- > > >> >>>> Rohit Saraf > > >> >>>> Second Year Undergraduate, > > >> >>>> Dept. of Computer Science and Engineering > > >> >>>> IIT Bombay > > >> >>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > >> >>>> On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal > > >> >>>> <[email protected]> wrote: > > > >> >>>>> On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf > > >> >>>>> <[email protected]> wrote: > > > >> >>>>>> are yaar... i meant BST... i thought that was obvious ! > > >> >>>>>> sry if i confused you.... > > > >> >>>>> @rohit It's ok.Actually in this group people come up with very > > >> >>>>> different and non-common solutions so its risky to take things > > >> >>>>> 'obviously'. > > >> >>>>> Rotation algo has a complexity of O(nlogn)[for constructing a BST] > > >> >>>>> +O(n) [for rotating n times]=O(nlogn) . > > > >> >>>>> Till now best algo we have is using heaps which give rise to > > >> >>>>> complexity > > >> >>>>> = O(n+klogn) > > > >> >>>>> Please pass on algos having better runtime complexity. > > > >> >>>>>> -------------------------------------------------- > > >> >>>>>> Rohit Saraf > > >> >>>>>> Second Year Undergraduate, > > >> >>>>>> Dept. of Computer Science and Engineering > > >> >>>>>> IIT Bombay > > >> >>>>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > >> >>>>>> On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal > > >> >>>>>> <[email protected]> wrote: > > > >> >>>>>>> Hey rohit.You were referring to Binary tree.Search keyword was > > >> >>>>>>> missing.Because rotation makes no sense in binary tree.Please > > note > > >> >>>>>>> binary tree and BST are different. > > > >> >>>>>>> On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf > > >> >>>>>>> <[email protected]> wrote: > > > >> >>>>>>>> Read the slides i uploaded. They explain what rotation does in > > a > > >> >>>>>>>> BST. > > > >> >>>>>>>> Also you might like to refer to Red Black Trees in CLRS.... > > that > > >> >>>>>>>> chapter explains rotations. > > > >> >>>>>>>> -------------------------------------------------- > > >> >>>>>>>> Rohit Saraf > > >> >>>>>>>> Second Year Undergraduate, > > >> >>>>>>>> Dept. of Computer Science and Engineering > > >> >>>>>>>> IIT Bombay > > >> >>>>>>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > >> >>>>>>>> On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf > > >> >>>>>>>> <[email protected]> wrote: > > > >> >>>>>>>>> but still the binary tree solution is of more practical use.i > > >> >>>>>>>>> will > > >> >>>>>>>>> explain the solution once i reach my comp > > > >> >>>>>>>>> On 4/11/10, Nikhil Agarwal <[email protected]> wrote: > > > >> >>>>>>>>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf > > >> >>>>>>>>> > <[email protected]> > > >> >>>>>>>>> > wrote: > > > >> >>>>>>>>> >> Time complexity is O(n log n). But the last solution I gave > > >> >>>>>>>>> >> has > > >> >>>>>>>>> >> O(n). > > > >> >>>>>>>>> >> What did u not understand abt thesolution > > > >> >>>>>>>>> > @Rohit Please explain how that Binary tree solution works. > > > >> >>>>>>>>> >> -------------------------------------------------- > > >> >>>>>>>>> >> Rohit Saraf > > >> >>>>>>>>> >> Second Year Undergraduate, > > >> >>>>>>>>> >> Dept. of Computer Science and Engineering > > >> >>>>>>>>> >> IIT Bombay > > >> >>>>>>>>> >>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > >> >>>>>>>>> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee > > >> >>>>>>>>> >> <[email protected]> wrote: > > > >> >>>>>>>>> >>> On 11 April 2010 10:46, Rohit Saraf > > >> >>>>>>>>> >>> <[email protected]> wrote: > > > >> >>>>>>>>> >>>> Construct a binary tree from the data (maintain the size > > of > > >> >>>>>>>>> >>>> subtree > > >> >>>>>>>>> >>>> under each node). > > >> >>>>>>>>> >>>> Do rotations till the left subtree does not have size k. > > >> >>>>>>>>> >>>> Rotation is a > > >> >>>>>>>>> >>>> constant time operation. > > >> >>>>>>>>> >>>> Please prove the correctness of your algorithm with the > > >> >>>>>>>>> >>>> time > > >> >>>>>>>>> >>>> complexity > > > >> >>>>>>>>> >>>> -------------------------------------------------- > > >> >>>>>>>>> >>>> Rohit Saraf > > >> >>>>>>>>> >>>> Second Year Undergraduate, > > >> >>>>>>>>> >>>> Dept. of Computer Science and Engineering > > >> >>>>>>>>> >>>> IIT Bombay > > >> >>>>>>>>> >>>>http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > >> >>>>>>>>> >>>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond > > >> >>>>>>>>> >>>> <[email protected]> > > >> >>>>>>>>> >>>> wrote: > > > >> >>>>>>>>> >>>>> nice solution appreciate it. but your algorithm is > > wasting > > >> >>>>>>>>> >>>>> time in > > >> >>>>>>>>> >>>>> finding all the element... > > >> >>>>>>>>> >>>>> instead of that just find boundary line kth element > > which > > >> >>>>>>>>> >>>>> can > > >> >>>>>>>>> >>>>> help as > > >> >>>>>>>>> >>>>> in finding element greater that kth and element small > > than > > >> >>>>>>>>> >>>>> kth and that > > >> >>>>>>>>> >>>>> soluton can be done in O(N) > > > >> >>>>>>>>> >>>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY > > >> >>>>>>>>> >>>>> <[email protected]> wrote: > > > >> >>>>>>>>> >>>>>> 1) Construct max heap by taking first k elements in an > > >> >>>>>>>>> >>>>>> array > > >> >>>>>>>>> >>>>>> 2) if k+1 element less than root of max heap > > >> >>>>>>>>> >>>>>> a) Delete root of max heap > > >> >>>>>>>>> >>>>>> b) Insert k+1 element in max heap and apply > > >> >>>>>>>>> >>>>>> heapify > > >> >>>>>>>>> >>>>>> method > > >> >>>>>>>>> >>>>>> 3) else skip the element > > >> >>>>>>>>> >>>>>> 4) apply above procedure for all n elements in an array > > > >> >>>>>>>>> >>>>>> At last you will get k smallest elements and root is > > kth > > >> >>>>>>>>> >>>>>> smallest > > >> >>>>>>>>> >>>>>> element in the array > > > >> >>>>>>>>> >>>>>> this is O(nlogk) > > > >> >>>>>>>>> >>>>>> ---------------------------------------- > > >> >>>>>>>>> >>>>>> CHERUVU JAANU REDDY > > >> >>>>>>>>> >>>>>> M.Tech in CSIS > > > >> >>>>>>>>> >>>>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy > > >> >>>>>>>>> >>>>>> <[email protected]> wrote: > > > >> >>>>>>>>> >>>>>>> Can any one tell how to do this when there are 'm' > > >> >>>>>>>>> >>>>>>> queries > > >> >>>>>>>>> >>>>>>> like > > >> >>>>>>>>> >>>>>>> "query i j k" find the kth largest element in between > > >> >>>>>>>>> >>>>>>> indices i->j in > > >> >>>>>>>>> >>>>>>> an array. > > >> >>>>>>>>> >>>>>>> When m is large even an O(n) algorithm would be slow. > > >> >>>>>>>>> >>>>>>> I thinking that each query could be answered in > > >> >>>>>>>>> >>>>>>> O(sqrt(n)) > > >> >>>>>>>>> >>>>>>> time > > >> >>>>>>>>> >>>>>>> So any suggestions ? > > > >> >>>>>>>>> >>>>>>> Thanks > > > >> >>>>>>>>> >>>>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond > > >> >>>>>>>>> >>>>>>> <[email protected]> > > >> >>>>>>>>> >>>>>>> wrote: > > > >> >>>>>>>>> >>>>>>>> there are better solution of O(n) are posted in the > > >> >>>>>>>>> >>>>>>>> thread.......[?]. > > >> >>>>>>>>> >>>>>>>> using order statices .... > > > >> >>>>>>>>> >>>>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur > > >> >>>>>>>>> >>>>>>>> <[email protected]> wrote: > > ... > > read more » > > 338.gif > < 1KViewDownload > > 361.gif > < 1KViewDownload- 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.
