Tournament TreesWinner Tree – DefinitionWinner Tree For 16 PlayersSlide 4Slide 5Complexity Of InitializeWinner Tree OperationsReplace Winner And ReplaySlide 9Slide 10Slide 11Loser TreeMin Loser Tree For 16 PlayersSlide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Complexity Of Loser Tree InitializeSlide 22Complexity Of ReplayTournament Tree ApplicationsTruck LoadingBin PackingSlide 27Bin Packing HeuristicsSlide 29Slide 30Slide 31PerformanceMax Winner-Tree For 16 BinsSlide 34Complexity Of First FitTournament TreesWinner trees.Loser Trees.Winner Tree – DefinitionComplete binary tree with n external nodes and n – 1 internal nodes.External nodes represent tournament players.Each internal node represents a match played between its two children; the winner of the match is stored at the internal node.Root has overall winner.Winner Tree For 16 Playersplayer match nodeWinner Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8Smaller element wins => min winner tree.3 6 1 3 2 4 2 53 1 2 2121Winner Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8height is log2 n (excludes player level)3 6 1 3 2 4 2 53 1 2 2121Complexity Of Initialize•O(1) time to play match at each match node.•n – 1 match nodes.•O(n) time to initialize n-player winner tree.Winner Tree Operations•InitializeO(n) time•Get winnerO(1) time•Replace winner and replayO(log n) time More precisely Theta(log n)•Tie breaker (player on left wins in case of a tie).Replace Winner And Replay4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 83 6 1 3 2 4 2 53 1 2 2121Replace winner with 6.Replace Winner And Replay4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 83 6 1 3 2 4 2 53 1 2 2121Replay matches on path to root.Replace Winner And Replay4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 83 6 1 3 2 4 2 53 1 2 2121Replay matches on path to root.Replace Winner And Replay4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 83 6 1 3 2 4 2 53 1 2 2121Opponent is player who lost last match played at this node.Loser TreeEach match node stores the match loser rather than the match winner.Min Loser Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8438Min Loser Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 84683517Min Loser Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 846835371629Min Loser Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8468353725281649Min Loser Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8468353725581649Min Loser Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8468353725581649Min Loser Tree For 16 Players4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 84683537255826494 3 6 8 1 5 7 3 2 6 9 4 5 2 5 84683537255826491WinnerComplexity Of Loser Tree Initialize•Start with 2 credits at each node.•Use one to pay for the match played at that node.•Use the other to pay for the store of a left child winner.•Total time is O(n).•More precisely Theta(n).Winner4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 84683537255826491Replace winner with 9 and replay matches.959332Complexity Of Replay•One match at each level that has a match node.•O(log n)•More precisely Theta(log n).Tournament Tree Applications•Run generation.•k-way merging of runs during an external merge sort.•Truck loading.Truck Loadingn packages to be loaded into truckseach package has a weighteach truck has a capacity of c tonsminimize number of trucksBin Packing•n items to be packed into bins•each item has a size•each bin has a capacity of c tons•minimize number of binsBin PackingTruck loading is same as bin packing.Truck is a bin that is to be packed (loaded).Package is an item/element.Bin packing to minimize number of bins is NP-hard.Several fast heuristics have been proposed.Bin Packing Heuristics•First Fit.Bins are arranged in left to right order.Items are packed one at a time in given order.Current item is packed into leftmost bin into which it fits.If there is no bin into which current item fits, start a new bin.Bin Packing Heuristics•First Fit Decreasing.Items are sorted into decreasing order.Then first fit is applied.Bin Packing Heuristics•Best Fit.Items are packed one at a time in given order.To determine the bin for an item, first determine set S of bins into which the item fits.If S is empty, then start a new bin and put item into this new bin.Otherwise, pack into bin of S that has least available capacity.Bin Packing Heuristics•Best Fit Decreasing.Items are sorted into decreasing order.Then best fit is applied.Performance•For first fit and best fit:Heuristic Bins <= (17/10)(Minimum Bins) + 2•For first fit decreasing and best fit decreasing:Heuristic Bins <= (11/9)(Minimum Bins) + 4Max Winner-Tree For 16 Bins84 3 6 8 1 5 7 3 2 6 9 4 5 2 5 84 8 5 7 6 9 5 87 9 8899Item size = 771Max Winner-Tree For 16 Bins64 3 6 1 5 7 3 2 6 9 4 5 2 5 84 6 5 7 6 9 5 87 9 899Complexity Of First FitO(n log n), where n is the number of