Construct a max-heap --> O(n)..
call delete() 2 times .. --> O(logn)..
===> O(n) time..
On Fri, Aug 31, 2012 at 1:46 AM, Don <dondod...@gmail.com> wrote:
> While the list length is more than one
> Take 2 elements from the head
> Select the larger of the two
> If the smaller is greater than the largest beaten by the larger
> Then set the largest beaten by the larger to the value of
> the smaller
> Add the larger to the tail of the list
>
> When this completes, you'll have one element containing the largest
> and second largest values.
>
> typedef struct
> {
> unsigned int value;
> unsigned int largestBeaten;
> } element;
>
> unsigned int secondLargest(queue<element> elements)
> {
> while(elements.length() > 1)
> {
> element A = elements.dequeue();
> element B = elements.dequeue();
> if (A.value < B.value) swap(A,B);
> if (A.largestBeaten < B.value) A.largestBeaten = B.value;
> elements.enqueue(A);
> }
> return queue.head().largestBeaten;
> }
>
> On Aug 30, 12:53 pm, sangeeta goyal <sangeeta15...@gmail.com> wrote:
> > @Don can you give the algorithm for the same??
> > how would you implement it??
> >
> >
> >
> >
> >
> >
> >
> > On Thu, Aug 30, 2012 at 10:03 PM, Don <dondod...@gmail.com> wrote:
> > > The second largest element is the largest element beaten by the
> > > winner.
> > > So if you implement a tournament in which each element keeps track of
> > > the largest element it has beaten, you'll get the second largest
> > > naturally.
> > > Don
> >
> > > On Aug 29, 9:15 am, Sangeeta <sangeeta15...@gmail.com> wrote:
> > > > give the algo or program to find second largest element in a list
> using
> > > > tournament method
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
