Here is a pseudo code.
Let the array be A[0..N-1].
Consider array B [0..2*N-2]. This array contains all the elements of the
binary tree formed from the tournament.
h = ceil ( log(N) base 2 ).
p = pow(2,h);
for( i=p-1,k=0; i<2N-1 ; i++,k++)
B[i] = A[k];
for(i=p-2, m =N-1; m>=k ; m--,i--)
B[i] = A[m];
for(i=p ; i<=2N-2 ; i+=2) {
B[i/2 - 1] = max(B[i], B[i-1]);
}
for(i=p/2 ; i>=2 ; i=i/2)
{
for ( k = 0;k < i ;k+=2)
{
B[ (k+i)/2 -1 ] = max( B[i+k], B[i+k-1]);
}
}
B[0] now contains the largest element.
Total no of comparisons done till now = N-1
Consider array C[0..h-1] . This contains all the candidates for second
largest element.
for(i=0, k=0;i<2N-1 ;k++ )
{
if( B[i] == B[2i + 1]) {
C[k] = B[2i+2];
i = 2i+1;
}
else
{
C[k] = B[2i + 1];
i = 2i + 2;
}
}
Now, the largest in the array C can be found in h-1 comparisons.
Total overall comparisons = (N -1) + (h-1), as required.
On Fri, Sep 18, 2009 at 9:54 PM, Nagendra Kumar <[email protected]>wrote:
>
> I want an algo for finding second highest element in n + log n- 2
> comparisons.
> The algo is first find the highest number and then highest among the
> number which get defeated during tournament.
> (details in corment).
>
> Can anyone do code implemenation for this one.
>
>
> Thanks
> Nagendra
>
> >
>
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
