00:07
okay all right any questions things
00:12
going all right so far all right so in
00:19
our last lecture we motivated the study
00:20
of several data structures one of these
00:23
is a tournament tree so today we will
00:26
take a close look at what the tournament
00:29
tree is and actually will see there are
00:31
two types of tournament trees there's a
00:32
loser tree and there's a winner's tree
00:34
we look at both of them and then we'll
00:37
take a look at an application of winner
00:40
trees to a bin packing problem okay and
00:47
of course in passing I'll also point out
00:49
how you can use say loser trees for one
00:52
generation okay I'm sorry not for run
00:55
generation but for merging runs all
00:58
right so so there are two types of
01:02
tournament trees there's a winner tree
01:04
and there's a loser tree a winner tree
01:07
is more intuitive than a loser tree and
01:10
a winner tree is something that you've
01:12
probably seen often pick up a newspaper
01:15
or read about a sports event you have a
01:18
bunch of players who enter a tournament
01:20
and then you have a tree like structure
01:22
where at each node you record who won a
01:25
match that was played at that node and
01:27
the match of that node was played
01:28
between the two children of that node
01:30
okay so for example in a tennis
01:32
tournament all right so let's take a
01:36
look at a winner tree basically for us
01:42
here a winner tree is going to be a
01:43
complete binary tree and I'll explain
01:47
what a complete binary trees in a moment
01:50
it's going to have two types of nodes
01:53
the first type called external nodes and
01:55
if you have n of these then there will
01:58
be n minus one of the second type those
02:01
are called internal nodes the external
02:04
nodes will represent the players in the
02:06
tournament and the internal nodes will
02:08
represent the matches that are played
02:15
right the best way to get a handle on
02:19
these these concepts is to look at an
02:22
example so let's take a look at an
02:25
example okay well so let's suppose you
02:28
have 16 players then I will have a
02:32
complete binary tree that has 16
02:36
external nodes and 15 internal nodes the
02:39
external nodes are the players so the
02:41
external nodes here are represented by
02:43
boxes square boxes the internal nodes by
02:47
circles now if you take a look at a
02:51
binary tree of a certain height which is
02:53
fully populated meaning that all the
02:55
nodes are present then if you number
02:57
those nodes top to bottom left to right
03:00
okay so for example this node will get
03:02
numbered 1 node 2 node 3 4 5 6 7 8 9 up
03:07
to 15 okay then if the nodes that are
03:13
present in a particular tree ok so what
03:18
I'm saying is you start with a fully
03:19
populated tree number the nodes top to
03:21
bottom left to right beginning with the
03:23
number 1 okay now suppose I'll give you
03:26
another binary tree and I look at those
03:30
nodes and compare them to this fully
03:33
populated one if the nodes that are
03:35
present are the nodes that were numbered
03:37
from 1 through n ok then I'll say that
03:40
you have a complete binary tree right so
03:44
for example here if you have the nodes 1
03:47
2 3 4 and 5 so it's just this whole
03:50
thing here okay including all of this
03:53
stuff ok then also you have a complete
03:55
binary tree with 5 nodes ok similarly a
04:00
complete binary tree with my nodes would
04:04
have so this is node 1 2 3 4 5 6 7 8 9
04:10
so if the nodes numbered 1 through 9 are
04:12
present and those are exactly the nodes
04:14
that you have then you have a 9 node
04:16
complete binary tree so if I give you
04:19
the number of nodes in the complete
04:21
binary tree the complete binary tree is
04:23
unique ok so they have exactly the nodes
04:26
that
04:26
with numbered 1 through m alright so
04:29
when a tree is a complete binary tree
04:31
and that complete binary tree is so if
04:41
you have 16 players it'll be a complete
04:43
binary tree on 15 internal nodes and
04:47
then wherever you have a null link in
04:50
that complete binary tree you put in an
04:52
external node which will be a player ok
04:56
so the way you get this tree is if you
05:01
know the number of players suppose it's
05:03
10 then you start with a complete binary
05:06
tree with 9 nodes and whatever there's
05:09
another link put in an external node and
05:12
there will be 10 such places so you'll
05:15
end up with 10 players and mine
05:16
internal nodes ok all right so our first
05:20
thing is given the number of players you
05:21
construct the structure of the tree and
05:26
then the players have values ok so in
05:33
the context of a computer implementation
05:36
the values will be same numbers at each
05:43
internal node I'm going to play a match
05:44
and that's going to be played between
05:47
the players at the child nodes of that
05:51
match node ok so to play a match for
05:54
example here I always take a look at the
05:56
values of the two children 4 and 3
05:59
they'll have to decide which of these
06:00
two wins some would have a rule for the
06:02
winner okay and the rule I'm going to
06:06
use is that the smaller of the two is
06:08
going to win ok so then you get
06:10
something that's called a min winner
06:12
tree if you change the rule to the
06:14
larger wins when you get a max you win a
06:16
tree all right so let's suppose I'm
06:19
building a min when a tree so the 3 and
06:21
the 4 will play at this point at this
06:23
match node and the smaller wins as 3 and
06:26
the smaller gets recorded right so a
06:31
similar to what might take place in a
06:33
tennis tournament two players will play
06:35
the winner gets recorded out here
06:39
well then we can look at this note here
06:41
you play a match over there between the
06:43
6 and the 8
06:44
the winner is 6 and that gets recorded
06:47
then I hop over to the next node okay
06:50
this one over here the 1 and the 5 will
06:53
play the winner is 1 then you play a
06:56
match here between the 7 and the 3 the 3
06:59
wins you play a match over here the two
07:02
wins over here the 4 wins over here the
07:06
2 wins and then over here the 5 will win
07:09
ok so you can view that as the
07:13
completion of one level of the
07:14
tournament well then when you advance to
07:18
the next level of the tournament so
07:23
we're going to play a match over here
07:26
and that match will be played between
07:29
the two children ok those are the
07:32
fellows that advance from this level of
07:33
the tournament to that level so over
07:35
here you play with the winners that's
07:37
the 3 and the 6 will play and the
07:41
smaller is going to win namely the 3
07:44
well then you come when you play over
07:46
here between the 1 and the 3 the
07:48
smallest one you play over there between
07:50
the 2 and the 4 the 2 wins you play over
07:53
there between the 2 and the 5 and the 2
07:55
wins ok and that completes the next
07:58
level of the tournament ok and then you
08:02
move on to play at this level and again
08:08
at each internal node the match is
08:10
played between the two fellows recorded
08:12
at the children nodes so the 3 and the
08:15
one will play the winner is 1 over here
08:18
the 2 and the 2 will play it's a tie so
08:21
you need some kind of a tie breaker and
08:24
depending upon the application you may
08:27
just have an arbitrary tie breaker which
08:29
says either can win in some applications
08:32
the tiebreaker is important and you
08:33
might say that the fellow on the Left
08:35
wins ok so one of these two two twos
08:40
will advance here depending upon the
08:42
tiebreaker and then finally there will
08:45
be in a finals match played up here
08:48
between the 1 and the 2 and the winner
08:50
is 1 and I'll
08:52
recorded alright so hopefully this kind
08:56
of structure looks very familiar to you
08:58
from following sports events and
09:02
basically at each internal node you
09:05
record the winner of the match played at
09:07
that node and then the route will end up
09:10
with the overall winner so in this case
09:13
it ends up with the smallest element one
09:24
or any questions about what a winner
09:27
tree is
09:32
in this example we had a nice number of
09:35
players of power of 216 but you can
09:38
build these trees independent of whether
09:40
the number of players is a power of 2 or
09:42
not now
09:49
when you actually go to implement one of
09:51
these fellows since you're dealing with
09:54
the complete binary tree it's very
09:57
efficient to implement these by mapping
10:00
the tree into an array like you take a
10:03
heap and you map that into an array
10:05
rather than using nodes with pointers so
10:09
this node would be stored in position 1
10:12
over an array position 2 over the array
10:14
position 3 and so on corresponding to
10:17
the numbering I described earlier you
10:21
can move up the node by just dividing by
10:23
2 okay
10:24
the parent of a node if you know the
10:26
index here this index is 8 so this
10:29
should be positioned for of the array
10:31
that's position 2 of the array okay so
10:34
you can move up by dividing by 2 if you
10:37
need to access your right sibling okay
10:40
you add 1 you need to access your left
10:43
sibling you subtract 1 ok so you can
10:46
move up and down get siblings by
10:49
performing simple arithmetic now in most
10:55
applications the players may be large in
10:59
size ok so for example if we're trying
11:03
to use this in a merging application so
11:07
maybe you're performing a 16 way merge
11:10
ok so then my players would be the 16
11:14
runs that are being merged and into the
11:17
tree I'll enter the first record in each
11:19
of those 16 runs so these are large
11:22
records the internal nodes will not
11:26
contain the full record rather this 3
11:29
here will be a pointer to this position
11:33
ok similarly this 3 here would be
11:36
appointed to that position this one here
11:38
would be a pointer to that position and
11:40
so on ok so the internal nodes will
11:44
typically not contain the full
11:46
player or the element but will typically
11:48
contain only a pointer to the place
11:51
where the record is stored because this
11:53
is a large record
12:05
alright the height of this structure is
12:07
a complete binary tree so the height is
12:10
going to be log of n base 2
12:18
alright let's take a look at the
12:20
complexity of initializing okay we just
12:23
saw an example where we initialize the
12:25
tree starting with 16 players basically
12:27
you have to play a match at each of the
12:29
15 internal nodes each match takes
12:33
constant time you have to compare the
12:35
value of the two children and then set
12:37
the appropriate pointer to the child at
12:40
one okay so each match takes one unit of
12:44
time there are n minus one match nodes
12:46
so n minus one matches so they're told
12:48
time to initialize the tree is order of
12:51
n or more precisely it's really theta of
12:53
N
13:01
let's look at the operations that are
13:03
winter tree supports okay the first
13:08
thing you need to be able to do is
13:10
initialize and we've seen how to do that
13:13
you need to be able to find out the
13:15
winner that stakes one unit of time
13:19
again think about a KY merge or in our
13:22
example 16 way merge when you're merging
13:26
16 runs you need to look at the front
13:28
records in these 16 runs and find out
13:30
which one has the smallest key so then
13:33
you want to know the winner of the 16
13:35
records okay and so the way we envision
13:39
doing the skyway merge is we start by
13:41
initializing a winner tree with 16
13:43
players and that would take 16 units of
13:46
time okay then I'll take the winner okay
13:50
and that winner has to be moved from its
13:53
current input buffer into an output
13:56
buffer okay
13:57
so I'll do a get when I find out who won
14:00
okay and once I find out who won I will
14:02
move the record from the input buffer
14:04
send to the output buffer okay once I've
14:08
made this move in that run the next
14:12
record advances and becomes the front
14:15
record so now you need to readjust your
14:18
winner tree okay so you need to do an
14:22
operation which is called a replace and
14:24
replay okay so we take the old winner
14:26
out and replace it by the fellow just
14:28
behind it in the run and now I need to
14:32
replay matches so that I have a proper
14:34
winner tree then I can take the winner
14:37
out again I do a get winner move it into
14:40
the output buffer replace the winner
14:42
with the record behind it in the run how
14:46
do you play matches and then do another
14:47
get winner
14:49
all right so that's the strategy they
14:52
have in mind for a keyway merge and
14:54
we'll see the replace winner and replay
14:57
matches is going to take logarithmic
14:59
time yeah
15:07
question what is the initialize consist
15:10
of the initialize is you're presented
15:13
with the 16 players and their values and
15:15
now you need to set up the window tree
15:17
okay so that's the little example we
15:19
went through before where I played the
15:21
15 matches and recorded in each node the
15:24
winner that's the in a short yeah that's
15:30
correct so the initialize isn't just
15:32
filling in the external nodes but it's
15:35
filling in the internal nodes okay so
15:37
typically you might be given say an
15:39
array of external nodes and then you got
15:42
to fill in the internal nodes okay
15:58
let's take a look at the replace winner
16:00
and replay operation okay alright so in
16:05
my case I started off with sixteen
16:06
players okay i initialized the tree okay
16:11
so I set up these fifteen values in the
16:14
gold boxes or circles and then this
16:17
fellow here told me that the overall
16:18
winners won so in the context of a
16:20
sixteen way merge that tells me that
16:22
this record has to move from its input
16:25
buffer into the output buffer okay and
16:28
seriously to find that because as I said
16:29
these numbers though it looks like I'm
16:32
storing the key values here I'm very
16:34
storing their a pointer so this is
16:37
really a pointer into this buffer okay
16:40
so what I've got down here my players
16:41
are sixteen buffers and I point to the
16:43
front record in the sixteen buffers okay
16:46
so following the pointer in the root I
16:48
end up here and that tells me that this
16:51
record has to be moved from this buffer
16:53
to the output buffer so I move it and
16:55
then the record that's just behind it
16:57
okay is going to enter the tree okay so
17:02
let's suppose that behind the one is a
17:04
six okay
17:07
so the six comes in and now I need to
17:09
set up a winner tree corresponding to
17:12
the players that are current so it's
17:14
really all of the old players except
17:17
that one has been replaced with six - to
17:24
modify my tree to reflect the new set of
17:26
winners I know that that the match
17:30
played here is not going to be affected
17:31
okay because the one was not involved
17:34
out here okay this man is not affected
17:37
that's not affected okay the only
17:40
matches whose outcome could possibly be
17:42
affected by changing the one to a six
17:44
are the nodes on the path from one up to
17:47
the root those are the places where the
17:49
one played okay so when the six enters
17:54
okay I need to replay the matches on the
17:58
path from here up to the root and find
18:01
out who is going to win over there those
18:04
are the places where one had played and
18:06
those are the places where the outcomes
18:08
going to change
18:13
alright alright so follow a path
18:16
starting from here okay I want to play a
18:19
match over here so I get my sibling okay
18:24
so the six and the five will play and
18:26
the winner is the five so the five is
18:31
going to get recorded over there okay
18:35
then I want to play a match here so you
18:38
play a match here I have to access my
18:40
sibling which is three the three and the
18:42
five will play out here
18:44
the winner is three so the three gets
18:46
recorded here then I move up here and to
18:50
play here I need to access the sibling
18:52
of this fellow so it's the three and the
18:56
winner was a three so you have a tie one
18:58
of the two threes is going to win and
19:00
the winner gets recorded here and then
19:02
you move up okay so to replace the
19:08
winner and replay I need to play login
19:12
matches starting from the parent of the
19:14
buffer which was the old winner okay and
19:18
play login matches starting from this
19:20
guy's parent going up to the root
19:23
each match takes one unit of time so it
19:27
takes you login to replay and Reece
19:30
restructure the tree and that's what we
19:36
used in our analysis of the last lecture
19:38
we said that if you use the tournament
19:40
tree then the number of compares needed
19:44
to determine who moves to the output
19:47
buffer next is log event base two rather
19:50
than n minus one from the simple
19:53
strategy or any questions about how to
19:59
use a winner tree to implement a K way
20:03
merge so that the comparisons poor
20:06
record moved from an input to an awkward
20:09
buffer is log K base two yeah
20:16
how is this differ different from a min
20:19
heap okay alright a in in a min heap you
20:31
don't have the concept that the value
20:34
that is stored here is the smaller of
20:37
the two children okay
20:38
the value in a node is the smallest in
20:41
the entire tree including itself okay so
20:44
in that sense it's a very different
20:47
structure we use the same min heap okay
20:55
now if you had a min heap for those
20:57
think about using a min heap for this
20:59
power okay
20:59
so if I hadn't been hey panda want to do
21:02
a K way merge I'll set up a min heap
21:04
with let's say let's say K 16 sub set up
21:06
a min heap with 16 elements all 16 will
21:09
be inside the heap itself so you don't
21:11
have the concept of external nodes okay
21:13
and so now the top has the minimum item
21:17
so you pull it out okay and then when
21:19
you get another item okay it's going to
21:21
move into the you have to find a place
21:26
for it inside this heap okay so you'll
21:28
do an insert at the top okay
21:31
which you can do okay so instead of
21:35
doing the traditional insert way
21:37
increasing the size of the heap here
21:38
you're not increasing the size of the
21:40
heap so you do an insert at the top and
21:44
you can do that insert also in
21:47
logarithmic time okay so you maybe do
21:49
accomplish the job in love with make
21:52
time what you cannot do with the main
21:54
heap is have a tie breaker okay so here
21:58
I can have a tie breaker
22:00
which will ensure for example things
22:03
like in some applications you want your
22:05
sort to be stable what that means is
22:08
that if you had two records with the
22:11
same value 10 and 10 then when you're
22:14
done with the sort whoever came first in
22:16
the input should still come first in the
22:18
output okay in a heap there's really no
22:23
way to enforce a tie breaker
22:27
but well here the the runs are numbered
22:35
okay so if this is 1 1 s 1 2 or 1 3 the
22:40
person on the left in case of a tie
22:43
always wins over the person on the right
22:51
in a heap no right but you don't have an
22:59
ordering on the nodes you don't have
23:02
external nodes to say who is on the left
23:05
and who's on the right ok if you want to
23:08
do it in a min heap you could add
23:09
another field which keeps the the run
23:13
number in there okay so in case of a tie
23:16
you let the fellow with a smaller run
23:17
number 1 ok ok
23:23
so you could certainly accomplish the
23:27
task with a min heap okay but you have a
23:33
problem with men heaps in terms of
23:35
putting in tie breakers well it's not a
23:48
question of explicitly defining
23:50
priorities the priority is essentially
23:52
are the values okay which you guys have
23:54
in both cases what you'd have to do
23:57
explicitly there is throwing I run
23:59
number okay which is implicit here which
24:02
comes in the positioning of the runs at
24:05
the bottom yeah
24:19
or the one can the matches will play
24:26
simultaneously well again it it depends
24:29
on whether you're thinking about say a
24:30
real world tournament of course it you
24:32
know the sixteen players can go out and
24:34
play at the same time so you have eight
24:36
matches and that's really what takes
24:37
place if you're thinking about a
24:39
computer context can they play at the
24:42
same time it depends on whether your
24:44
hardware supports parallel computation
24:57
well the other advantage you have here
25:04
over a heap is that these nodes only
25:10
have to be pointers to elements that are
25:12
stored in input buffers okay in the case
25:15
of a heap you would probably have to
25:17
store the elements inside the heap all
25:24
right so let me go back to that okay all
25:33
right now here if you look at the replay
25:37
operation okay
25:38
what's required in the replay operation
25:41
is if you're out here and you want to
25:44
replay this match okay you need to
25:47
access the sibling okay so the access a
25:49
sibling you need to know are you at an
25:51
odd position or an even position if you
25:54
had an even position your siblings to
25:56
the right so you add one if you're in an
25:59
odd position you subtract one to get to
26:01
the sibling okay so you have to access a
26:04
sibling and then once you access the
26:06
sibling you move up to the parent and
26:07
record the winner here okay so to play a
26:11
match you have to access a parent to
26:13
record the winner you have to access a
26:14
sibling to find out who you're playing
26:16
against the sibling that you are
26:22
accessing okay so when you bring the
26:24
match out here you'll notice that
26:28
previously when the match was played
26:30
here the three had played between the
26:33
one okay and the three lost the match
26:36
okay similarly when you come here to
26:39
play a match doing the replay the
26:42
previous match that was played here was
26:43
between this three and the one I
26:45
recorded the winner that's one with the
26:47
three lost okay next time when you come
26:50
during the replay and you want to play
26:51
the match here whoever's coming from
26:54
this side is going to have to play with
26:55
who lost the match the previous time
26:58
okay and so what that tells you is if
27:01
instead of storing winners at these
27:03
nodes if you stored losers okay then
27:06
when I'm coming up to replay
27:08
then over here the five is going to be
27:10
sitting so I don't need to access the
27:11
sibling okay the five is sitting here
27:13
you play the match with the five record
27:15
the loser the winner comes up and plays
27:17
with whoever lost here before namely the
27:19
three you don't have to access the
27:20
sibling okay we will see that an example
27:24
that motivates having a different
27:30
tournament tree somewhat non-intuitive
27:35
it's a loser tree where in each node you
27:39
store the loser rather than the winner
27:45
all right so let's take a look at
27:48
setting up the tournament tree with
27:52
losers rather than winners and the way
27:56
I'm going to do this is again I'm going
27:58
to sweep down the bottom okay
28:00
so first I'll play a match here okay
28:03
I'll play a match there play a match
28:05
there and so on but when you're playing
28:07
a match at a node as you'll see we'll
28:10
end up playing as many matches as
28:11
possible at ancestor nodes okay so it's
28:16
not going to have the same nice pattern
28:18
that the previous initialize had where
28:22
you went
28:23
node by node level by level okay but as
28:28
you'll see it's complexity is going to
28:30
be the same okay all right so I apply
28:33
out here the loser is the four so record
28:37
the four rather than the three okay now
28:40
the winner is three and that's going to
28:42
be needed later to play a match over
28:44
here okay the reason I know it's going
28:48
to be needed later you can't play a
28:50
match out here yet is to play the match
28:52
over here you must have already played
28:54
this one okay since this is an even
28:58
position it's right sibling has yet to
29:01
be seen because I'm going left to right
29:03
so I'm going to record the three out
29:06
there temporarily okay later it's going
29:10
to get replaced by whoever loses all
29:14
right then I come to this position here
29:16
okay
29:17
the six and the eight will play the
29:20
loser is the eight
29:22
the winner is the six six marches up to
29:24
play since it's coming from the right
29:27
child there's already somebody waiting
29:30
there you know that because the left
29:32
child is seen before the right child in
29:34
this left to right scan okay so you know
29:37
there's somebody waiting to play so you
29:39
play with the three so the six and the
29:41
three will play the six loses gets
29:43
recorded here the three moves up to play
29:45
at the next level since it's coming from
29:48
a left child the three has to wait well
29:54
then I come over here the 1 and the 5
29:56
we'll play the one wins the five losses
29:59
and waits sorry and gets recorded the 1
30:02
moves up to play at the next level but
30:04
it's coming from a left child so it has
30:06
to wait then you come over here the 7
30:11
and the three will play the 7 loses and
30:13
gets recorded the 3 moves up here to
30:16
play the three and the one play the
30:18
three loses and gets recorded the one
30:21
moves up here to play it's coming from
30:23
the right so somebody waiting for it the
30:27
three loses gets recorded here the one
30:30
wins and moves up it's coming from a
30:32
left child so it has to wait well then I
30:36
come over here the two and the six will
30:39
play the six loses the two moves up to
30:43
play since it's coming from a left child
30:45
the two has to wait then the four and
30:49
the nine will play the nine loses the
30:53
four moves up to play since it's coming
30:55
from a right child there's a player
30:57
opponent waiting there so the two and
30:59
the four play the four loses the two
31:02
moves up and waits then I come over here
31:08
so the two and the five will play the
31:12
five loses and gets recorded the two
31:14
moves up there and waits then we come
31:17
down here the 5 and the 8 we'll play the
31:21
eight loses the five moves up it loses
31:25
against the tools that gets recorded the
31:28
two moves up there's a tie so one of the
31:31
two twos wins
31:34
the other two moves up here to play with
31:36
the one the two loses the one wins and
31:42
if you record the one if you're using an
31:45
array you swap position zero you stuff
31:47
the one in there to record the winner
31:56
all right so loser tree is a tournament
32:00
tree in which at each match node you
32:01
record the loser and then you have a
32:04
special node in which you record the
32:05
overall winner
32:19
right again these numbers that looks
32:23
like I'm showing keys in reality you
32:25
will be storing pointers to the
32:26
appropriate buffers right questions
32:38
about what a loser tree is
32:52
look at the complexity of the initialize
33:00
to figure out the complexity okay
33:06
certainly one could use the worst case
33:08
analysis which would say well when
33:12
you're out here you spend log n time
33:14
playing all those matches and the number
33:18
of internal nodes at the bottom level is
33:20
like n over 2 so that's n log n but a
33:25
better analysis comes from using say the
33:30
techniques that we developed for
33:34
amortized analysis you could for example
33:36
use an aggregate scheme just somehow
33:37
figure out the total time spent or what
33:41
we do in this case is make use of the
33:45
idea of credits ok so what I'm going to
33:48
do is I'm going to start by placing two
33:51
units of credit at every match node ok
33:54
so that's a total of say 2 n minus 2
33:59
credits over there and if necessary I'll
34:11
put two units of credit on the overall
34:13
winner making it a total of 2n credits
34:17
ok and then what I'll do is whenever
34:20
some work is done I will charge against
34:22
those credits and if none of those
34:24
credits drops below zero then I know
34:27
that two end credits was enough to pay
34:28
for all of the work and so the
34:30
complexity is 2n ok so I start with
34:36
about two end credits place it on all of
34:38
those internal nodes at the rate of 2
34:41
per node and then whenever work is done
34:44
I'm going to charge against those
34:45
credits so at a node ok
34:50
for example this node of that node you
34:53
play a match so that cost you one and
34:56
you store a loser and I cost you one
35:03
if you look at all of the work that's
35:04
done in this thing it's basically
35:07
playing matches and storing losers and
35:09
storing winners okay so when you play a
35:15
match okay okay so if you play a match
35:17
so we might count playing a match and
35:19
storing the losers one unit of work okay
35:23
so I play a match and store the loser
35:25
that's one unit of work I store the
35:28
winner I could either count that as part
35:29
of that one unit or I could count it
35:31
separate and say I'm going to charge
35:33
that one to the place where you store
35:35
the winner okay so in this analysis I'm
35:37
charging the storage of the winner to
35:39
the node where you store the winner all
35:43
right so I've got two units one unit is
35:45
used to play to pay for playing the
35:47
match at the node and storing the loser
35:49
at the node the other unit is going to
35:54
be used if you store a winner and that
35:56
node okay so if you store a left child
35:59
winner and that takes care of all the
36:06
work that's done in the algorithm so
36:12
starting with two units of credit for
36:14
every node I can pay for all of the work
36:16
and so the overall complexity sort of
36:20
and I started with two end credits
36:24
certainly you have other ways of doing
36:26
it you could start with one unit of
36:27
credit per node it's just a question of
36:29
how you divide out the work and how you
36:31
charge it alright so even when you're
36:39
not trying to do an amortized analysis
36:41
the credit scheme could be useful
36:47
okay I also got the replace winner
36:55
operation so the overall winners stored
36:59
in that special node out there that's
37:02
the one and so that's pointing me down
37:04
to this fellow here and I'm going to
37:07
replace it with a nine okay so now I
37:12
need to restructure the tree so that it
37:15
is a proper loser tree for the new set
37:17
of players the new set of players is the
37:20
same as the old set except that one of
37:22
the fellows has changed it was a 1 it
37:23
became a 9 as before I have to replay
37:27
the matches on the path from here up to
37:29
the root the difference this time is I
37:34
don't need to access siblings on the way
37:36
up so I play a match here the person
37:43
have to play with is waiting for me
37:44
there is the fellow who lost the match
37:46
the last time it was played there so the
37:48
mind will play with the 5 the 9 loses
37:51
and gets recorded over there as a loser
37:54
the 5 moves up to play here again the
37:58
person you had to play with is waiting
37:59
out there you don't access a sibling so
38:01
the 5 plays against the 3 the 5 loses
38:04
the 3 wins and moves up here and plays
38:08
against the person waiting there it's a
38:10
tie one of the two threes wins and moves
38:13
forward the other one gets recorded here
38:15
the 3 that wins moves up and plays with
38:18
the 2 and the 3 losers the 2 wins and
38:24
the 2 becomes the overall winner
38:36
all right so the process is very similar
38:39
to what was used in the winter tree the
38:41
difference being that you don't access
38:42
siblings on the way up which means that
38:45
you will run faster by some constant
38:48
factor it's still a log in process but
38:54
faster by a constant factor all right so
39:03
complexity is the same you play one
39:05
match at each level it's log n levels to
39:10
play at and so that works out to Theatre
39:14
of log n to replay the matches all right
39:23
questions about loser trees
39:34
okay all right so let's look at some
39:36
applications we saw one well one that we
39:39
look at next time is run generation look
39:43
at that next time one that we talked
39:48
about when we were doing the examples is
39:50
K way merging of runs yeah now these are
39:57
tournament trees in general okay so and
40:03
we all look at some of them here so you
40:06
can use certainly in these two
40:10
applications a loser tree will get you
40:12
better performance than a winner tree
40:19
another one that we're going to look at
40:21
in the balance of today's lecture is a
40:22
truck loading problem which is really a
40:25
an instance of a bin packing problem and
40:30
here we'll see that to implement one of
40:33
the heuristics for truck loading a loser
40:36
so not a loser but a winner tree is a
40:38
good way to go all right so let's look
40:42
at the truck loading problem okay as you
40:45
have a fleet of trucks and you have a
40:49
whole bunch of packages that need to be
40:51
shipped to some destination the packages
41:01
have a weight associated with them and
41:03
each truck has a capacity can't carry
41:06
more than C units of weight so the
41:11
objective is to find the smallest number
41:13
of trucks you need so that you can load
41:16
all of these packages into them without
41:18
violating the capacity constraint of a
41:20
truck
41:26
okay
41:33
any question about what the problem is
41:34
so you want to minimize the number of
41:36
trucks they can carry all of the goods
41:38
that need to be sent all right so this
41:47
is an instance of a abstract problem
41:50
called a bin packing problem here you're
41:52
given some number of bins and some
41:56
number of items the items need to be
41:58
packed into the bins each item has a
42:00
size associated with it and each bin has
42:03
a capacity okay and you want to minimize
42:05
the number of bins so in the bin packing
42:10
problem you have items to be packed into
42:14
bins each item has a size each bin has a
42:16
capacity you want to minimize the number
42:18
of bins so transforming it into the
42:27
abstract problem each truck is a bin in
42:29
each package is an item that's got to be
42:32
packed into a bin and you want to
42:33
minimize the number of bins the number
42:35
of trucks but the problem of minimizing
42:41
the number of bins required is a
42:45
difficult problem you've probably heard
42:47
of the term np-hard
42:48
if you haven't it doesn't really matter
42:50
are you hear about it in the algorithms
42:54
class if you for sure
42:55
and basically np-hard problems have the
42:58
property that one no fast solution or no
43:02
polynomial time solution is known to
43:04
them and there are I guess literally
43:08
thousands of problems that people like
43:11
to solve that are known to be np-hard
43:13
and the current wisdom is that none of
43:18
these are solvable in polynomial time
43:20
now there's a subclass of those called
43:22
np-complete which have the property that
43:24
if you could solve any one of those in
43:25
polynomial time then every other one
43:28
could be done in polynomial time as well
43:31
alright so this is a problem that's
43:35
known to be hard it's a problem that
43:37
people don't expect will be solvable by
43:41
a fast algorithm and as a result people
43:46
focus on heuristics where heuristics
43:50
could take one of two different forms in
43:53
one form you look for a fast algorithm
44:00
it's always fast but it may not get you
44:02
the best solution in the other form you
44:06
look for a solution that always gets you
44:08
the best but sometimes it's fast and
44:10
sometimes it's slow
44:13
all right the heuristic we're going to
44:15
look at here is of the first type it's
44:17
always fast but it doesn't guarantee the
44:19
best solution the whole bunch of
44:23
heuristics that have been proposed for
44:25
bin packing first one is one called
44:27
first fit so in this basically you order
44:32
your bins from left to right you look at
44:36
the items one at a time and the item
44:42
that you're currently looking at you put
44:43
it into the leftmost bin into which it
44:45
fits okay so you line up the trucks left
44:49
to right put the packages and put into
44:51
the leftmost truck into which it fits if
44:54
it doesn't fit into a truck that's
44:56
currently in use you start a new one all
45:02
right then there's first fit decreasing
45:03
which is really the same as first fit
45:05
except you order the items in decreasing
45:07
order of size before you start the
45:09
process
45:13
there's best fit which seems to do a
45:16
little bit more work you still look at
45:18
the items one by one but then you look
45:21
at the bins that are there and you find
45:25
the one into which the fit is best which
45:26
means the either unused capacity after
45:30
you put it in is the smallest and if
45:37
there's no bin and use with this
45:39
property that it fits you start a new
45:41
bin
45:48
well you have best fit decreasing to the
45:50
same as best friend except you first
45:52
sort the jumps sort the items in
45:55
decreasing order now in terms of
46:01
performance one can prove and the proofs
46:04
are yet to be fairly complicated but
46:06
I'll rescue their results if you use
46:08
either first fit the best fit then you
46:12
use at most 70% more bins than you need
46:14
to if you use the decreasing version
46:19
then you use at most about 20% more bins
46:22
than you need to okay and these are
46:25
worst-case bounds if you take any random
46:26
instance then you usually get very close
46:30
to the minimum number of bins so you're
46:32
not off by 70 percent or 20 percent but
46:36
you could have pathological examples
46:38
where you would be 70 percent off or 20
46:40
percent off all right so our interest
46:46
here is really to see how we would
46:47
implement either best fit or first fit
46:50
now to implement best fit we're going to
46:54
need a data structure that we're going
46:55
to study later but to implement first
46:58
fit efficiently we can use a max winner
47:00
tree now let's see how that works okay
47:03
suppose we have 16 bins okay that we're
47:07
using for packing and let's suppose this
47:09
is the current state these numbers here
47:11
give me the amount of capacity that's
47:12
left in a bin okay so the first bin has
47:15
4 units of space the next one has 3
47:17
units of space this one's got 6 units of
47:19
space so max when a tree is an internal
47:23
node I record the larger of the two
47:24
children ok similarly here record the
47:28
larger of the two children so the fellow
47:32
in the root gives me the maximum
47:34
capacity available in any bin ok
47:37
similarly the 8 out here tells me in the
47:40
first eight bins the maximum available
47:43
capacity is 8 the 7 here tells me that
47:45
in this collection of four bins the
47:47
maximum capacity available is 7
47:52
right now suppose you want to pack and I
47:55
go whose size is seven using first fit I
48:00
want to find the leftmost bin into which
48:02
it fits namely this one sorry this one
48:11
okay so I want to find this one it's the
48:13
leftmost bin into which it fits okay do
48:16
you find that I'm going to start at the
48:17
top of my tree okay so we start out here
48:21
the line here tells me there's at least
48:23
one bin somewhere into which it fits
48:25
because I got a bin whose capacity is 9
48:26
that's the maximum I'm going to prefer
48:30
to bin in the left half over a bin in
48:32
the right half because first fit says
48:35
find the leftmost one the 8 tells me in
48:38
the first half I've got somebody's
48:39
capacity is 8 and so the 7 can be
48:42
serviced from somebody in the left half
48:45
so I move here if this number had been a
48:47
4 I wouldn't come here I would go to the
48:49
other side okay all right so now I'm
48:52
here I'm going to prefer somebody in the
48:55
left half over the right half down here
48:57
I've got 8 so I move down here it's
48:59
enough to service the 7 from here I
49:02
would prefer the left half of the right
49:04
half but the best in the left half is
49:06
for that's not enough so I got to move
49:08
here ok
49:11
and so you follow a path from the top to
49:13
the bottom preferring to go to the left
49:15
if there's enough capacity moving to the
49:17
right if there isn't
49:17
eventually you'll reach a bin so in this
49:22
case I will reach this bin ok and takes
49:26
me log n time to end up down here once
49:28
I've reached this bin I need to update
49:30
capacities I'm going to use up 7 units I
49:33
will be left at 1 okay so the capacity
49:37
left here is decreased and then I need
49:40
to reflect the winners on the path from
49:43
the root to here so I'll retrace going
49:47
back up ok playing a winner so 6 and the
49:51
one who play the six wins over here the
49:54
4 and the 6 will play the six wins over
49:57
here the 6 and the 7 will play the 7
49:59
wins and then over there the seven and
50:01
the nine will play the nine wins ok so
50:03
that restructures my winner tree
50:06
and now I'm ready to do the next
50:08
assignment okay so you can find the
50:14
leftmost bin into which somebody fits in
50:16
logarithmic time and you can update the
50:19
tree so you're ready to do the next
50:21
assignment
50:28
all right so if you are packing n items
50:34
we will start with n bins all being
50:36
empty that's the maximum number of bins
50:38
you need to set up a max winner tree
50:40
with n bins so take me order n time to
50:44
initialize the structure and then log n
50:46
time for each assignment because the
50:48
height of the tree is log n so your
50:51
total complexity is order n log n ok any
51:02
questions ok we'll stop you