@shiv here we go
to find 2nd best player in array
Tournament tree is a form of min (max) heap which is a complete binary
tree. Every external node represents a player and internal node
represents winner. In a tournament tree every internal node contains
winner and every leaf node contains one player.maxheap is winner tree
& min heap is looser tree.
There will be N – 1 internal nodes in a binary tree with N leaf
(external) nodes.
It is obvious that to select the best player among N players, (N – 1)
players to be eliminated, i.e. we need minimum of (N – 1) games
(comparisons). Mathematically we can prove it. In a binary tree I = E
– 1, where I is number of internal nodes and E is number of external
nodes. It means to find maximum or minimum element of an array, we
need N – 1 (internal nodes) comparison. its simple fact of
mathematics.
The method is tournament algorithm. The idea is to conduct a knockout
minimal round tournament to decide the ranks. It first organises the
games (comparisons) between adjacent pairs and moves the winners to
next round until championship (the first best) is decided. It also
constructs the tournament tree along the way. Now the second best
element must be among the direct losers to winner and these losers can
be found out by walking in the binary tree in O(log n) time. It
organises another tournament to decide the second best among these
potential elements. The third best must be one among the losers of the
second best in either of the two tournament trees. The approach
continues until we find k elements. This algorithm takes O(n + k log
n) complexity, which for any fixed k independent of n is O(n).
for example check it let say we have array a={5,3,8,7} & we have build
given tournament tree using above algo
8(Winner)
/ \
5 8 to find 2nd best we have to choose the
path by winner in 2nd last step ??
/ \ / \
5 3 8 7
its clear that 1st max or min element can't be done in less then O(N)
in an unsorted array isn't it ?
now to find the 2nd best choose the pat of direct looser to winner
then go through this path until we reach to leaf , as leaf nodes
always be player compare them & maximum will be 2nd maximum here try
out it for different example so what the total number of comparisons
to find 1xt maximum its n-1 = O(N)
to find 2nd maximum logn-1=O(logn) as we start comparing after root
tottal number of comparisons is n-1+logn-1=n+logn-2
let me know if i missed something ??
Thanks
Shashank Mani
Computer Science & Engg.
Birla Institute of Technology Mesra
--
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.
