In K way Merging , we implement Heap sort . You can go through the link http://www.site.uottawa.ca/~nat/Courses/DFS-Course/DFS-Lecture-9/tsld021.htm
Tournament tree also uses Heap . For it's implementation we need sorted set of arrays and need to precalcuate the height of the tournament tree . Suppose u have got 5 set of sorted array we can find the height of the tree by ceil(log 5) = 3 . Now at level 3 , there will be 2^3=8 leaf nodes and we have 5 set of array .The leaf nodes will contain 5 pointers to the set of each sorted element and the remaining 3 leaf node is marked a infinity. So the value of the leaf node will be equal to the first element of each set . Now pair up the leaf nodes to find the parent nodes one level up in the tree . The value of the parent node will be equal to the min(left set element , right set element ) or max(left set element , right set element ) depending on the order u follow . Keep on pairing the new parent nodes until single node is encountered . the value . The value of the root node will give the 1st winner . Similarly for getting the next winner we need to repeat the process , after setting the leaf node of the to the next value in the set from which the 1st winner was present , until the all the leaf node are emptied . Can refer to http://www.geeksforgeeks.org/archives/11556 -- 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.
