**Tournament Trees**CSE, POSTECH**Tournament Trees**• Used when we need to break ties in a prescribed manner • To select the element that was inserted first • To select the element on the left • Like the heap, a tournament tree is a complete binary tree that is most efficiently stored using array-based binary tree • Used to obtain efficient implementations of two approximation algorithms for the bin packing problem (another NP-hard problem) • Types of tournament trees: winner & loser trees**Tournament Trees**• The tournament is played in the sudden-death mode • A player is eliminated upon losing a match • Pairs of players play until only one remains • The tournament tree is described by a binary tree • Each external node represents a player • Each internal node represents a match played • Each level of internal nodes defines a round of matches • Tournament trees are also called selection trees • See Figure 13.1 for tournament trees**Winner Trees**Definition A winner tree for n players is a complete binary tree with n external nodes and n-1 internal nodes. Each internal node records the winner of the match. • To determine the winner of a match, we assume that each player has a value • In a min (max) winner tree, the player with the smaller (larger) value wins • See Figure 13.2 for winner trees**Winner Trees**The height is log2(n+1) (excludes the player level) Whatkind of games would use (a) min winner tree? Whatkind of games would use (b) max winner tree?**Winner Tree Operations**• Select winner • O(1) time to play match at each match node. • Initialize • n-1 match nodes • O(n) time to initialize n-player winner tree • Remove winner and replay • O(log n) time**Winner Tree Sorting Method**• Read Example 13.1 • Put elements to be sorted into a min winner tree. • Remove the winner and replace its value with a large value (e.g., ∞). • replay the matches. • If not done, go to step 2.**Sort 16 Numbers**1. Initialize the min winner tree**Sort 16 Numbers**2. Remove the winner and replace its value**Sort 16 Numbers**3. Replay the matches**Sort 16 Numbers**Remove the winner and replace its value**Sort 16 Numbers**Replay the matches**Sort 16 Numbers**Remove the winner and replace its value**Sort 16 Numbers**Replay the matches**Sort 16 Numbers**Remove the winner and replace its value Continue in this manner….**Time To Sort**• Initialize winner tree: O(n) time • Remove winner and replay: O(logn) time • Remove winner and replay n times : O(nlogn) time • Thus, the total sort time is O(nlogn)**Exercise 1 – [3, 5, 6, 7, 20, 8, 2, 9]**• Max Winner Tree • Min Winner Tree • After the change, the max winner tree becomes: • After the change, the min winner tree becomes: Is this correct?**The ADT WinnerTree**• Read ADT 13.1 for Winner Tree ADT specification • Read Program 13.1 for the abstract class winnerTree**The Winner Tree Representation**• Using the array representation of a complete binary tree • A winner tree of n players requires n-1 internal nodes tree[1:n-1] • The players (external nodes) are represented as an array player[1:n] • tree[i] is an index into the array player and gives the winner of the match played at node i • See Figure 13.4 for tree-to-array correspondence**Determining the parent of external node**• To implement the interface methods, we need to determine the parent tree[p] of an external node player[i] • When the number of external nodes is n, the number of internal nodes is n-1 • The left-most internal node at the lowest level is numbered s, where s = 2log2(n-1) • The number of internal nodes at the lowest level is n-s, and the number LowExt of external nodes at the lowest level is 2*(n-s)**Determining the parent of external node**• What is n and s for Figure 13.4? • Let offset = 2*s - 1. Then for any external node player[i], its parent tree[p] is given by p = (i +offset)/2 i LowExt p = (i – LowExt + n –1)/2 i LowExt**Loser Trees**Definition A loser tree for n players is also a complete binary tree with n external nodes and n-1 internal nodes. Each internal node records the loser of the match. • The overall winner is recorded in tree[0] • See Figure 13.5 for min loser trees • Read Section 13.4**Figure 13.5 Eight-player min loser trees**Example Min Loser Trees What is wrong with the min loser tree (b)?**Exercise 15 – [20, 10, 12, 18, 30, 16, 35, 33, 45, 7, 15,**19, 33, 11, 17, 25] • Max Loser Tree • Min Loser Tree • After the change, the max loser tree becomes: • After the change, the min loser tree becomes:**Bin Packing Problem**• We have bins that have a capacity binCapacity and n objects that need to be packed into these bins • Object i requires objSize[i], where 0 < objSize[i] binCapacity, units of capacity • Feasible packing - an assignment of objects to bins so that no bin’s capacity is exceeded • Optimal packing - a feasible packing that uses the fewest number of bins • Goal: pack objects with the minimum number of bins • The bin packing problem is an NP-hard problem We use approximation algorithms to solve the problem**Truck Loading Problem**• Have parcels to pack into trucks • Each parcel has a weight • Each truck has a load limit • Goal: Minimize the number of trucks needed • Equivalent to the bin packing problem • Read Examples 13.4 & 13.5**Bin Packing Approximation Algorithms**• First Fit (FF) • First Fit Decreasing (FFD) • Best Fit (BF) • Best Fit Decreasing (BFD)**First Fit (FF) Bin Packing**• Bins are arranged in left to right order. • Objects are packed one at a time in a given order. • Current object is packed into the leftmost bininto which it fits. • If there is no bin into which current object fits,start a new bin.**Best Fit (BF) Bin Packing**• Let bin[j].unusedCapacity denote the capacity available in bin j • Initially, the available capacity is binCapacity for all bins • Object i is packed into the bin with the least unusedCapacity that is at least objSize[i] • If there is no bin into which current object fits,start a new bin.**First Fit Decreasing (FFD) Bin Packing**• This method is the same as FF except that the objects are ordered in a decreasing size so that objSize[i] objSize[i+1], 1 i < n**Best Fit Decreasing (BFD) Bin Packing**• This method is the same as BF except that the objects are ordered as for FFD**Bin Packing Example**• Assume four objects with objSize[1:4] = [3, 5, 2, 4] • Assuming each bin’s capacity is 7, what would the packing be if we use FF, BF, FFD, or BFD? • FF • Bin 1: objects 1 & 3, Bin 2: object 2, Bin 3: object 4 • BF • Bin 1: objects 1 & 4, Bin 2: objects 2 & 3 • FFD • Bin 1: objects 2 & 3, Bin 2: objects 1 & 4 • BFD • Bin 1: objects 2 & 3, Bin 2: objects 1 & 4 • Read Example 13.6**First Fit Bin Packing with Max Winner Tree**• Use a max winner tree in which the players are n bins and the value of a player is the available capacity binCapacity in the bin. • Read the section on First Fit and Winner Trees on pp. 521 & See Figure 13.6 for first-fit (FF) max winner trees • See Program 13.2 for the first-fit bin packing program**First Fit Bin Packing with Max Winner Tree**• Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} 1 1 5 1 3 5 7 10 10 10 10 10 10 10 10 1 2 3 4 5 6 7 8 Initial bin[tree[1]].unusedCapacity >= objSize[1]?**2**2 5 2 3 5 7 2 10 10 10 10 10 10 10 1 2 3 4 5 6 7 8 After objSize[1]=8 packed First Fit Bin Packing with Max Winner Tree • Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[2]=6 be packed into?**3**3 5 2 3 5 7 2 4 10 10 10 10 10 10 1 2 3 4 5 6 7 8 After objSize[2]=6 packed First Fit Bin Packing with Max Winner Tree • Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[3]=5 be packed into?**4**4 5 2 4 5 7 2 4 5 10 10 10 10 10 1 2 3 4 5 6 7 8 After objSize[3]=5 packed First Fit Bin Packing with Max Winner Tree • Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[4]=3 be packed into?**4**4 5 1 4 5 7 2 1 5 10 10 10 10 10 1 2 3 4 5 6 7 8 After objSize[4]=3 packed First Fit Bin Packing with Max Winner Tree • Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[5]=6 be packed into?**5**3 5 1 3 5 7 2 1 5 4 10 10 10 10 1 2 3 4 5 6 7 8 After objSize[5]=6 packed First Fit Bin Packing with Max Winner Tree • Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[6]=4, objSize[7]=2 and objSize[8]=7 be packed into?**More Bin Packing with Max Winner Tree**• Exercise – Do the same example using BF, FFD, BFD with Max Winner Tree • Do Exercise 13.23 • READ Chapter 13