Heap's good but the i think problem clearly mentions "Tournament sort" use this https://blogs.oracle.com/malkit/entry/finding_kth_minimum_partial_ordering
although you can do a Inplace tournament sort ...swapping the corresponding elements level 1. adjacent pairs level 2: between pairs apart by 1 place n so on (2,4,8..) until there is only one element left in there without a pair.....this gives u least element Now instead of using a "Multimap" , use a simple array with size equal to original array and store the element that defeated each corresponding element. Get all those elements defeated by the least element ... that number should be of order O(n) get the second least element out of it in O(n) time. *Shashi Kant * *"Think positive and find fuel in failure"* http://thinkndoawesome.blogspot.com/ *System/Software Engineer* *Hewlett-Packard India Software Operations. * On Wed, Sep 5, 2012 at 4:11 AM, Dave <[email protected]> wrote: > @Don: Nope. Constructing a heap can be done in O(n). See, e.g., > http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html > . > > Dave > > On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote: > >> Constructing a max-heap is O(n*log n) >> >> However, the problem asked for a solution using tournament method. >> If you ignore that requirement, an O(n) solution is trivial, and >> doesn't require the additional storage of a heap: >> >> int first = max(A[0], A[1]); >> int second = min(A[0], A[1]); >> for(i = 2; i < N; ++i) >> { >> if (A[i] >= first) >> { >> second = first; >> first = A[i]; >> } >> else if (A[i] > second) >> second = A[i]; >> } >> >> // First and second now contain 1st and 2nd largest values in A >> >> Don >> >> On Sep 3, 5:04 am, bharat b <[email protected]> wrote: >> > Construct a max-heap --> O(n).. >> > call delete() 2 times .. --> O(logn).. >> > ===> O(n) time.. >> > >> > >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/bKzs-wHLSoIJ. > > 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.
