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 <nagendra....@gmail.com>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 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 -~----------~----~----~----~------~----~------~--~---