Transcript


00:00
Oh
00:15
Thank You graded first assignments and
00:20
I'm sure you've if you've got them back
00:23
you've probably try to go through them
00:24
and see how the grading was done now
00:26
there is a solution set that's posted on
00:29
the web so you do want to take a look at
00:33
the sample solution set compare that
00:35
with the answers you gave now if you're
00:39
not happy with the grading what you want
00:41
to do is you want to first talk to the
00:43
grader this mr. Lu and see if you can
00:45
resolve your differences with him and if
00:48
you can't then please bring the material
00:50
to me and we'll go over it and we should
00:53
be able to resolve it at that time okay
00:55
now again there is an exam scheduled for
00:58
Friday the exam is structured quite like
01:03
the sample tests that are there on the
01:05
web and we do plan to give you about 60
01:11
minutes to do it so you want to be sure
01:14
that you get here on time and that you
01:18
can in fact spend a few minutes extra
01:20
now you don't really need 60 minutes as
01:24
I said before if you have prepared for
01:27
it you should be able to do all the
01:31
problems in 50 minutes are a lot less
01:33
than that if you haven't prepared for it
01:35
60 or 90 minutes are not going to be
01:38
enough to do it so I don't really think
01:42
anybody's going to be here after the 50
01:44
minutes but just in case the intention
01:47
is to let you hang around if you do want
01:49
a few extra minutes okay all right any
01:52
questions
01:57
all right so today we're going to take a
02:01
look at the last structure we're looking
02:02
at for single ended product queues this
02:06
one was called a herring heap now the
02:10
pairing heap supports all of the
02:12
operations supported by the Fibonacci
02:14
heap and if we compare the Fibonacci and
02:21
pairing heaps first with respect to
02:25
their actual complexity okay we see that
02:28
as far as the actual complexity is
02:31
concerned the pairing heap seems to have
02:36
a better actual complexity for the
02:38
decrease key which is order 1 instead of
02:40
order n and then the actual complexity
02:42
on the remaining operations is the same
02:45
as that for the Fibonacci heap you know
02:49
a comparison on actual complexities is
02:52
probably not a very worthwhile
02:54
comparison because we know the Fibonacci
02:56
heap is lousy as far as actual
02:57
complexity per operation is concerned
02:59
and really the same is true for pairing
03:02
heaps if you have an actual complexity
03:04
of order n that's not a great thing for
03:06
an operation the merit of the Fibonacci
03:10
heap is really because of its amortized
03:14
complexity so let's take a look at that
03:16
comparison so as far as amortized
03:20
complexities go the best bounds that are
03:25
known for the amortized complexity of
03:27
their pairing heap operations are
03:29
actually log n for each one of them now
03:34
it's not knowing that those are tight
03:36
bumps so maybe somebody can prove better
03:38
bounds but what what is known is that
03:40
there's no way you can achieve the
03:42
bounds of the Fibonacci heap so there
03:44
are lower bounds on the amortized
03:45
complexity of pairing heap operations
03:47
which essentially say that if the
03:50
amortized complexity for insert is order
03:52
1 well then you can't have I mean if you
03:56
make this thing order 1 then you can't
03:58
have the same numbers on that side
03:59
somebody's got to be bigger ok so as far
04:05
as proving complexities is concerned
04:09
the upper bounds of that the log end
04:12
that's known that a lower bounds known
04:14
will show that the pairing heap cannot
04:16
match the fibonacci heap from the
04:20
amortized complexity point of view okay
04:22
now if you know that then you might say
04:26
well why bother to look at the structure
04:28
okay since it's provable it's probably
04:32
inferior the reason is that this is
04:37
probably one case where one has to go
04:41
back and take a look at the meaning of
04:42
complexities and realize that if you
04:47
have some algorithm whose complexities
04:49
let's say order then you got another
04:50
round with them whose complexities order
04:52
of n square it might just be that for
04:55
all practical cases that you want to
04:57
solve the order n square is better than
04:59
the order n because of constant
05:01
coefficients that are multiplying the N
05:04
and the N square and that's what turns
05:07
out over here that the experimental
05:11
studies that have been done using
05:13
pairing heaps versus Fibonacci heaps in
05:15
places like Dijkstra's shortest path or
05:17
prims greedy spanning tree algorithm
05:22
those indicate that if you use pairing
05:24
heaps you actually get reduced run time
05:27
compared to using Fibonacci heaps so
05:32
working with large graphs it just turns
05:37
out that because of the simplicity of
05:39
the pairing heap even though it's
05:41
asymptotic the asymptotic bounds and
05:45
amortized complexity or not as good it
05:48
happens to give a better performance
05:50
okay so something to keep in mind the
05:52
analysis has limitations okay so let's
05:58
take a look at the pairing heap it's
06:04
simpler to implement that in part
06:07
results and it's having better observed
06:10
run time
06:15
and it's more space efficient the total
06:19
number of nodes used is the same one
06:21
node per element but the number of
06:23
fields in your node is smaller okay
06:25
so experimentally you have better run
06:28
time and it's easy to see theoretically
06:32
that the space is less well that's a
06:37
definition again you have two types of
06:39
paring heaps you have the min and the
06:41
max depending upon whether you want a
06:43
min priority queue or a max priority
06:46
queue and it's basically just a single
06:52
tree okay whereas a Fibonacci heap was a
06:55
collection of min trees or a collection
06:56
of max trees here you have a single min
06:59
tree or a single max tree we take a look
07:07
at the max version so far we've been
07:08
consistently looking at the min so I'm
07:10
going to make a switch here and look at
07:11
a max version okay it doesn't really
07:14
matter which version you look at there
07:17
are they're pretty much the same all
07:18
right so I got a max tree here this is a
07:20
candidate for being a max pairing heap
07:30
the note structure we're going to adopt
07:33
each note is going to have a child
07:35
pointer which you point to the first
07:38
child from amongst this list of children
07:44
we're going to have left and right
07:46
sibling pointers because we're going to
07:48
keep the siblings in a doubly-linked
07:49
list this will not be a circular list
07:53
out to be it simply a doubly linked list
07:58
since it's not a circular list the left
08:02
sibling pointer of the first node serves
08:07
no useful purpose I mean it would
08:11
normally be now because there's nobody
08:13
else left we'll find a better use for it
08:15
than setting it to null okay similarly
08:19
the right sibling pointer of the last
08:21
node serves no useful purpose it's now
08:23
other than telling you it's the last
08:25
node but we're not going to find any
08:28
other use for that all right so the left
08:35
sibling pointer of the first node
08:37
instead of being set to null is actually
08:40
going to be used to point to the parent
08:42
as a result we're not going to have
08:46
parent fields okay only one node will
08:49
point to the parent and that's the left
08:51
most node okay the remainder won't we'll
08:58
be able to tell if you're sitting at the
09:00
first node okay if you look at its left
09:04
child if you look at its left sibling
09:10
pointer if it's the first node the left
09:12
sibling pointer should go to the parent
09:14
and then the child pointer of the parent
09:16
should come to the first node so should
09:18
come back to this fellow okay so if you
09:22
perform this check okay
09:24
so X dot left that gets you to the
09:26
parent supposedly if it is the leftmost
09:28
fellow and then you follow the child
09:31
pointer in the parent if it gets you
09:32
back to X then X was the leftmost note
09:35
if it doesn't get you back to X then you
09:38
were not at the left most node okay so
09:41
you don't really need
09:42
you have a null pointer in the left
09:44
field of the left most node to tell that
09:46
you're at the left most node alright so
09:50
we're going to use the left pointer in
09:52
the left most node really as a surrogate
09:54
parent pointer there will be a data
10:00
field which keeps the element and that's
10:04
it okay so we're going to have these
10:08
four fields a data field left and right
10:11
sibling fields and child the fields were
10:17
saving compared to a Fibonacci heap
10:20
we're saving the parent the degree and
10:22
the child cut field so as a reduction in
10:27
about three fields as a result the total
10:31
space needed by pairing heaps is less
10:39
all right let's see how we perform the
10:41
various operations okay again we're only
10:46
going to look at how the operations are
10:47
done I'll be able to establish the
10:50
actual complexity of the operations in
10:52
class we will not go through the
10:53
amortized complexity analysis all right
11:01
the key operation and thering heaps is
11:03
the MELD okay so in a meld you're given
11:06
two pairing heaps and you need to
11:08
combine them into one and that's used
11:12
that's done using something called the
11:14
compare linked operation and what you do
11:17
is it's a lot like comparing it's a lot
11:21
like combining two trees of equal degree
11:23
in the case of Fibonacci heaps okay but
11:29
here the two trees may not have the same
11:30
degree okay
11:32
so compare link is done on two trees
11:34
whose degree Amman may or may not be
11:37
equal what you do is you compare the two
11:41
roots and since you want to build a max
11:43
tree the fellow with the smaller root
11:45
becomes a child of the fellow with the
11:47
bigger root okay so if you have this as
11:53
one of your max trees
11:55
that is the other will compare the two
11:58
routes
11:58
this fellow is smaller so this needs to
12:01
become a subtree of the night okay and
12:03
will become the leftmost subtree okay so
12:13
it's it's pretty much the same as what
12:16
was being done in the fibonacci heap
12:18
when you combine two trees together the
12:21
only difference is that here the degrees
12:24
of the trees may not be the same
12:37
all right so as far as melding two trees
12:40
is concerned it takes you only order one
12:45
time to do it okay you do the comparison
12:49
and then this has to join the doubly
12:54
linked circular list here as the
12:56
leftmost fellow and that's quite easy to
12:58
do you need to change a child pointer
13:01
using the child pointer you can get here
13:03
and then you can insert it at the left
13:04
and set the appropriate parent pointer
13:07
back the parent pointer is in fact the
13:11
Left sibling pointer oh it's any
13:15
questions about the milk it's an order
13:20
one operation
13:30
look at insert but very much like how
13:33
you might insert in a Fibonacci heap you
13:39
create a one element max tree like you
13:42
would out there and then you do a mode
13:48
okay so if that's my existing max tree
13:53
or Fibonacci heap I want to insert it
13:55
too I'll create a node that has the two
14:00
in it and then do a compare linked
14:02
operation okay so since two is smaller
14:06
than nine it'll become the left leftmost
14:09
child of nine so you create a single
14:21
node pairing heap with a new item and
14:24
then compare link it with the original
14:27
tree here's another example
14:36
okay this time I want to insert a 14 so
14:40
I'll compare I'll create they're pairing
14:42
heap with a single item 14 then compare
14:46
link those two pairing heaps together
14:48
since the nine is smaller than the 14
14:50
the mine will become the leftmost child
14:53
of the 14th so again order 1
15:07
alright so the actual cost of an insert
15:10
is order one any questions about insert
15:22
alright suppose we do inserts in this
15:25
fashion and actually there's going to be
15:27
no extra work done unlike Fibonacci
15:32
heaps where we later came and started to
15:34
do cascading cuts that's all that we're
15:37
going to be doing so knowing how the
15:41
insert works we can arrive at bounds on
15:44
the degree as well as height of pairing
15:48
heaps okay so suppose you insert items
15:53
in this order decreasing order okay well
15:57
then you first create a current heap
16:00
that has a nine okay and then one with
16:02
eight and you pair it will compare link
16:05
them so eight will become the leftmost
16:06
child of mine okay
16:08
and then when the seven comes in it will
16:09
become the new leftmost child of mine
16:11
and then six will become the new
16:13
leftmost child of mine and so on so
16:15
you're going to end up with okay so a
16:18
eight becomes the child and seven and
16:21
then six and finally up to one so again
16:26
that you'll end up with a tree that has
16:29
only two levels in it if you put in a
16:31
total of n items the root will have n
16:33
minus one children alright so unlike
16:38
binomial in Fibonacci heaps the degree
16:40
here is not constrained by log of the
16:42
number of elements
16:50
if you look at the height right suppose
16:54
you insert your items in the other order
16:56
increasing order okay right so one goes
17:01
in you get a single element pairing heap
17:04
then you bring in the two you do a
17:07
compare link one becomes a child of two
17:11
then you bring in the three the two
17:13
becomes a child of three okay then comes
17:17
in the for the three becomes a child of
17:19
four okay and so on so the height of
17:30
this becomes n okay so as far as pairing
17:38
heaps are concerned they have the worst
17:40
possible degree and the worst possible
17:43
height okay yet from the amortize point
17:50
of view they give you good performance
17:53
we're good here means logarithmic for
17:56
all operations what if all elements are
18:05
equal the tiebreaker you can use is
18:09
arbitrary just pick one say it's bigger
18:11
than the other we're using well they
18:20
we're certainly using priority because
18:22
when elements come in when you do the
18:24
compare link you compare the priority of
18:26
to operate of two elements and the
18:29
fellow with the smaller priority becomes
18:31
a child of the fellow with the bigger
18:32
one in case of a tie you take any one
18:44
but by value of the element I mean the
18:46
priority of the element okay
18:54
okay all right so the worst case height
18:58
is n the worst case degrees n minus 1
19:00
and you can't get any worse than that
19:06
let's take a look at the increased key
19:09
operation so to increase the key
19:14
somebody has a pointer external to you
19:16
and they give you that pointer in the
19:18
node and they tell you how much to
19:20
increase it by and when you increase the
19:26
value as far as the subtree rooted at
19:28
that node is concerned it remains a max
19:30
tree okay the problem was with respect
19:33
to the parent your value might now
19:35
become bigger than that in the parent
19:37
and unfortunately there's no way for you
19:40
to check that except when you are the
19:42
leftmost sibling or the leftmost child
19:45
because you don't have a parent field ok
19:50
so since you can't check what you do is
19:52
you assume the worst has happened and
19:54
you cut yourself off from your parent ok
19:59
so here you always cut yourself off from
20:03
the parent was in Fibonacci heaps you
20:05
first do a check and you cut yourself
20:07
off only if you have to ok all right so
20:10
here you're going to cut yourself off
20:13
regardless
20:19
all right so I've been asked to increase
20:23
the key at for whether you've been asked
20:25
to increase it by zero or one or ten it
20:29
doesn't really matter because there's no
20:31
way for you to check that the new key
20:33
you have here is bigger than your parent
20:36
or is smaller than your parent and
20:39
there's no efficient way to check
20:41
certainly you could follow pointers left
20:44
pointers and come all the way here and
20:46
then check okay but we're not going to
20:48
bother to do that we're just going to
20:51
detach okay all right so regardless of
20:55
what you increase it to that subtree is
20:57
detached you pull it out of its doubly
20:59
linked list and that's an order one
21:02
operation you do have to be careful if
21:06
you're pulling out the leftmost fellow
21:07
for example this guy okay then you have
21:11
to change the child pointer in the
21:13
parent so it points to the next fellow
21:18
all right so we're going to detach
21:34
well once you detach okay
21:38
then I will compare link with what's
21:44
left and create a new tree
21:57
okay so in the compare lengths you look
22:01
at the two routes the smaller route
22:02
becomes the leftmost child or the fellow
22:04
the bigger route ties are broken any way
22:06
you like all right so that's the
22:10
sequence of steps any questions about
22:13
how we propose to implement the
22:16
increased key operation the constraint
22:24
is that yeah the value of the amount
22:26
cannot be negative and the reason you
22:29
have that constraint of course is that
22:30
if you decrease okay if you decrease the
22:34
value you can't ensure that you have a
22:40
max tree okay so if I give you a
22:46
negative value for the amount this could
22:48
for example drop to zero and then you
22:50
have a problem with this subtree in
22:52
which case you've got to go downwards to
22:54
fix that problem okay and that increases
22:57
the complexity okay so as was the case
23:02
for Fibonacci heaps the requirement is
23:05
the amount is a non-negative number
23:12
other questions will increase key all
23:21
right if you look at the complexity I
23:24
need to detach this fellow to do the
23:32
detach since it's a doubly linked
23:33
circular list you can pull it out in
23:36
order one time if it was in the doubly
23:39
link circular list we can't use the
23:43
trick we talked about when we were
23:45
looking at binomial heaps which said
23:46
copy from the forward fellow because
23:48
there are pointers external to the
23:50
structure which say my four is sitting
23:52
in this node okay similarly that our
23:55
pointers which say my two is sitting out
23:57
here and if you move the two from there
23:58
to here the external pointers become
24:01
invalid okay so we can't use that copy
24:04
trick you have to physically play with
24:06
that node okay and that's why we have a
24:08
doubly linked list
24:11
okay well so you can detach in order one
24:14
time and then you have to do the compare
24:18
link which is another order one
24:21
complexity operation so the actual cost
24:28
is order one okay so the meld the insert
24:40
and the increased key operation all have
24:43
an actual complexity of order one now
24:52
let's look at the remove max operation
24:54
since we're dealing with the max tree
24:57
the max item is in the root so take that
25:00
item and throw it out and once you throw
25:03
it out you're left with potentially
25:06
large number of sub trees that have to
25:08
be melded into a single tree okay all
25:13
right so why first empty you got nothing
25:15
otherwise you take the root out and you
25:17
have to Mel the sub trees into a single
25:18
tree and here is where you need to be
25:23
careful about how you do the melding if
25:28
you do the melding using what we call a
25:30
good way then you can prove log n
25:34
amortize complexities if you do the
25:37
melding in what we call a bad way you
25:40
can prove order n amortize complexity is
25:42
the best okay so I guess the trick if
25:51
you want to call it a trick in this
25:52
structure is how you do the melding of
25:55
sub trees following your remove max and
25:59
also following an arbitrary remove which
26:01
we'll see in a moment let's first take a
26:07
look at a bad way and for this we will
26:10
see that the amortized complexity the
26:11
best provable amortize complexity is
26:14
order n
26:19
all right so a bad way is I've taken out
26:24
the root and let's say I'm left with ten
26:26
subtrees so I picked one of these let's
26:29
say the first one and make that the
26:30
current tree and then I'll go through
26:32
nine rounds of melding the remaining
26:34
trees one by one into what's the current
26:35
tree okay so we start with the first
26:39
tree then for each of the remaining
26:40
trees do the compelling operation to
26:44
meld the next tree into the current tree
26:46
that gives you the new current tree okay
26:48
and that seems to be the simplest way to
26:51
do it also an intuitive way to do it so
26:55
for example if this is your pairing heap
27:04
you do remove max the mind goes out okay
27:11
when the nine goes out we're left with
27:13
these sub trees then I take the eight on
27:18
metal the six compare link the six into
27:20
it and compare link two for the two of
27:22
the one and so on okay
27:27
so we'll end up with that okay so yeah
27:31
start with eight compare link the sixth
27:33
sin it becomes the first child then you
27:35
put in for it becomes a new leftmost
27:37
child you put in two it becomes a new
27:39
leftmost child and so on we end up with
27:41
that structure so the total number of
27:48
compare links we had to do here we were
27:51
left with two four six eight so I had to
27:54
do seven compare links now suppose you
27:58
do another remove max okay so you take
28:01
out the eight okay and then we'll start
28:07
with seven five will become its first
28:09
child and then three will become its new
28:11
first child or leftmost than one then
28:13
two then four and then six okay so
28:16
that's going to take six compare links
28:20
okay and the structure you're going to
28:23
be left with after that okay it's
28:26
against the metric to what you started
28:28
with except you got two fellows less
28:31
you've lost the eight and you lost the
28:32
seven but you've got the six four two
28:34
one three five okay you do another Mel
28:40
that's going to take you I guess five
28:44
compare links so you do another remove
28:46
max
28:46
then you do want to take you four and so
28:48
on okay so if you look at this
28:51
particular example you do a sequence of
28:52
remove Max's each remove max we'll take
28:57
one less compare length in the previous
28:59
one so if you started with about n items
29:02
in there the first one might do n minus
29:04
1 then n minus 2 and minus 3 and so on
29:11
all right so the actual cost of an
29:13
insert so let's say now we start at
29:15
Ground Zero you got nothing okay and I'm
29:18
going to do a bunch of inserts okay and
29:24
and then after the inserts I'm going to
29:26
do a sequence of remove maxes and
29:29
they'll take a look at the time for this
29:31
whole sequence so I'm going to do a
29:33
bunch of inserts each insert is going to
29:35
cost me one I'm also going to do a bunch
29:39
of remove maxes and the cost of each
29:41
remove max is the degree of the root so
29:49
I'll do an over two inserts in this
29:51
order that will give me the initial tree
29:54
that I put up so I expand that sequence
29:56
so that it's of size n over two and then
30:04
I'll do an hour to remove maxes right so
30:07
this example is for the case where n is
30:09
I guess mine yeah we're in over two is
30:15
mine so n is 18 and here n is the total
30:18
number of operations in the sequence
30:20
alright so and n is 18 n over 2 is mine
30:24
I do nine inserts that gives me the tree
30:27
I had up before then I'll do nine to
30:29
remove Max's bringing it down to an
30:31
empty tree so the inserts cost you one
30:37
each I'll do an over two of those using
30:40
the expanded version of that sequence
30:42
does it cost me an over two
30:44
then I'll do my n over to remove Max's
30:50
the first one will cost me n over two
30:54
minus one because that's the degree of
30:56
my tree so for example here the degree
31:00
of the tree is eight even though there
31:03
were nine items or nine inserts okay so
31:05
the first remove max will cost me at
31:07
over two minus one the next one will
31:09
cost me over two minus two then n over
31:11
two minus three and finally down to one
31:14
for the last one alright so the cost of
31:21
the remove Max's works out to be 0 of n
31:24
square so from this example what you see
31:30
is that if you claim that the amortized
31:36
cost of an insert is 1 okay then the
31:40
only way you can end up with a total
31:42
sequence cost of n over 2 plus n square
31:44
is if the amortized cost over remove max
31:48
is n of order event some constant times
31:52
n okay so if the amortized cost of an
31:57
insert is order 1 then the amortized
31:59
cost of an insert marks of a remove max
32:01
has to be theta of N and since we
32:10
claimed that but similarly if the
32:14
amortized cost of an insert is log n
32:17
okay then the no.2 inserts only give you
32:20
n log n the only way to get n square is
32:23
if the amortized cost ever removed max
32:25
is n okay similarly if the amortized
32:33
cost ever removed max is log n the
32:35
amortized cost of an insert has to be n
32:39
otherwise you can't get the n square
32:41
total sum
32:48
all right so from this example what we
32:51
see is that one of these two operations
32:54
the insert or remove max has to have an
32:57
amortized cost that is order of n
33:01
otherwise you can't pay for the total n
33:03
square cost all right any questions
33:07
about that right so if we handle the
33:15
remove max in the way we just did this
33:20
you simply are not going to have a
33:22
structure that has an amortized
33:23
complexity of order n for each of the
33:25
operations it's got to be order n for at
33:28
least the insert or the remove max okay
33:33
all right so that way of doing a remove
33:35
max isn't any good well there's several
33:43
good ways to melt these trees which give
33:46
you which allow you to prove log n
33:49
amortize complexity for each of the
33:51
operations we'll take a look at two of
33:54
them the two pass scheme and the multi
34:00
pass scheme doesn't matter which one you
34:07
use the best bounds known are log n for
34:11
all of the operations the experimental
34:18
results seem to indicate that the first
34:20
of these gives you slightly better
34:23
performance in terms of actual measured
34:27
runtimes
34:32
let's look at the to pass scheme so in
34:35
the first pass you examine the subtrees
34:37
that you have so you take out the route
34:38
they left with a bunch of sub trees
34:40
examine them from left to right and meld
34:44
pairs of them together so you compare
34:46
linked pairs of them and that reduces
34:49
the number of trees to about half in
34:55
case you have an odd number then you
34:57
take the remaining fellow and compare
35:01
link it in to the last fellow you had
35:03
from the step here it will look at an
35:07
example to make clear what we're doing
35:10
once you've reduced the number of trees
35:12
to half then you run the bad scheme
35:17
essentially okay so you take the
35:21
rightmost subtree generated here call it
35:23
the working tree we were calling it
35:24
current tree and then meld the remaining
35:27
fellows into it one by one okay so the
35:33
main difference between this and the bad
35:35
scheme is that you have a pre pass where
35:38
you cut the number of trees to half by
35:40
melding them in pairs and then you run
35:43
essentially the bad scheme okay let's
35:48
look at an example okay all right so I
35:52
suppose I've got eight trees okay so
35:54
I'll compare link the first two together
35:57
I'll compare link the next to the next
36:01
two in the next two reducing the number
36:05
of trees to half if they had a t9 I
36:09
would compare link the t9 with s4 at
36:12
this time okay so again you end up with
36:17
half of the number of trees a little bit
36:20
less than half all right that's the
36:24
first pass
36:29
in the second pass you take a look at
36:32
the results from the first pass you
36:34
start with the rightmost fellow compare
36:37
link it with the fellow before it then
36:41
you compare link it with the fellow
36:42
before it and compare link it with the
36:44
fellow before it
36:59
all right so that's the to pass scheme
37:08
any questions about the two passkey
37:20
all right again there's nothing really
37:22
intuitive about it what was intuitive
37:24
was the bad scheme but the bad scheme is
37:27
bad for a good reason it's got bad
37:30
amortized complexity okay here again why
37:35
do you do it this way well the only
37:37
reason to do it this way is when you do
37:39
it that way people can prove that the
37:41
amortized complexity is logarithmic for
37:44
each of the operations or the multi path
37:53
scheme but this looks a lot like the way
37:58
you would say initialize I left this
38:03
tree if you recall what we were doing
38:06
there was you start with n elements you
38:09
create one element left as trees
38:10
toss them into your queue pull them out
38:12
two at a time combine them into one ball
38:16
dome into one put it on the back of you
38:17
we're going to do the same thing out
38:19
here take our trees toss them into a
38:22
queue pull them out two at a time
38:23
comparing put them in the back keep
38:25
doing this till you're done all right so
38:30
take your take the trees left after you
38:33
toss out the root toss them into a queue
38:36
and then we have a step that gets
38:42
repeated till you're left with a single
38:43
tree you pull two trees from the front
38:46
of the queue compare link them put the
38:51
result into the back of the queue so
38:59
each iteration of this reduces the
39:01
number of trees by one if you started
39:04
with ten trees after nine trees you'll
39:06
be left with one and you're done
39:12
all right so I've got eight trees put
39:18
them in a queue I pull out t1 and t2
39:21
compare modem get s1 put it in the back
39:24
pull out t3 and t4 compare meld them get
39:27
s to put them in the back pull out two
39:31
from the front t5 and t6 compare meld
39:34
them compare link you get s3 put it in
39:37
the back you pull out t78
39:40
from the front compare link you get an
39:43
s4 put it in the back okay now if you
39:48
had an odd number say t9 you would take
39:50
t9 and compare link it with s1
39:53
okay once you've got them in the queue
39:57
you just repeat that basic step pull out
39:59
two at a time
40:01
compare link of meld and put them put
40:04
the result in the back so now you pull
40:06
out s1 s2 meld or compelling put in the
40:10
back pull out s3 s4 get in our to one
40:14
more steps needed pull out to put back
40:18
one and you're done all right so that's
40:24
the same as how we were initializing
40:25
leftist trees again here there's a proof
40:34
around that shows that if you do you're
40:37
recombining of the trees that are left
40:39
following the remove max throwing out
40:41
the root the amortized complexity is log
40:44
in for all of the operations the actual
40:53
cost is order n because the degree can
40:56
be as much as n minus 1 so you throw out
40:58
somebody got degree n minus 1 you've got
41:00
to look at all of them let's order of n
41:01
time
41:06
all right we have one operation left
41:09
that's to remove an arbitrary element if
41:12
it's the root you handle it like you're
41:14
doing a remove max if it's not the root
41:15
we need to handle it differently okay so
41:21
we take it out of its doubly linked list
41:26
of siblings and when you take it out you
41:33
got to throw away the node itself so
41:36
that gives you a bunch of sub trees that
41:38
it had we need to combine them together
41:41
into one so we'll do that either using
41:44
the two parts of the multi path scheme
41:45
so whatever strategy you adopt for the
41:48
remove max will adopt the same one here
41:50
and after you've done that will meld it
41:54
with whatever was left after you pulled
41:57
it out from the main tree okay let's
42:00
look an example to illustrate how this
42:02
works all right so I've been asked to
42:10
take this item and throw it away the way
42:14
I'm going to do that is I'm going to
42:15
pull this whole tree out of its doubly
42:18
linked list like I did for an increase
42:20
key however in an increased key the
42:24
number of elements didn't change we
42:25
don't have to throw the node away here I
42:27
got it throw the motorway and that's
42:28
going to give me these two sub trees
42:34
alright so I take it out of its doubly
42:36
linked list that's an order one
42:37
operation you get that and we're to take
42:42
the root and toss the root away and
42:44
that's going to leave me with some
42:45
number of sub trees which could be of
42:47
the same order as the total number of
42:49
elements or total number of operations
42:51
you've done so far and then in this case
42:56
I'll be left with two sub trees I'm
42:58
going to combine them into one using
43:00
either the two parts of the multi pass
43:02
scheme
43:09
in this particular case it doesn't
43:11
matter which scheme you use there only
43:12
two trees to combine you get the same
43:14
result you end up with that and once
43:20
you've done that we'll then
43:21
Mel this with the big tree whatever
43:25
okay this fellow here to end up with a
43:27
single tree so you do a compare link the
43:30
three is smaller than the mine so it's
43:32
going to show up as the leftmost child
43:35
of the night
43:45
okay all right questions about removing
43:49
an arbitrary element given a pointer to
43:53
the node which hazard right the actual
44:02
complexity of this is order n mainly
44:05
because when he threw away the node
44:07
it could have order of n children so
44:11
unlike the increase key which was order
44:14
1 this is an order n operation okay any
44:25
questions yeah yeah what's the
44:36
difference between the two in terms of
44:38
why one is called good and one is called
44:40
bad or of the mechanics my question is
44:52
what's the difference between the good
44:54
way in the bad way the if you're looking
44:58
at an individual remove max operation
45:02
okay so that individual to remove max
45:04
operation takes the same amount of time
45:07
whether you do it the good way of the
45:09
bad way it's the same number of compare
45:11
links the difference comes about when
45:14
you try to establish an amortized
45:15
complexity so you look at a sequence of
45:17
these for the bad way the example we saw
45:21
showed that there's no way anybody can
45:25
prove the amortized complexity is
45:27
logarithmic because it isn't okay the
45:29
amortized complexity for the insert or
45:32
the remove max one of these two
45:34
operations has to be order n okay so for
45:38
what I call the good way using either
45:41
the multi pass of the two way there are
45:43
proofs around which show that the
45:45
amortized complexity is log n which is
45:47
the same as saying that no matter how
45:49
hard you try you will not be able to
45:51
come up with an example where the cost
45:54
of a sequence of n operations is n
45:57
square
45:58
every sequence of n operations will take
46:00
n log n time now we haven't seen the
46:05
proof so it's kind of it's kind of hard
46:08
to maybe convince you mathematically of
46:11
that fact but that there is a proof
46:12
around way can you get the proof if you
46:20
check the readings there's a citation to
46:22
the original paper that developed there
46:25
in heaps so if you pull out that paper
46:27
it's got the scale the whole proof that
46:30
suddenly if you go to the web and do a
46:32
google search you'll probably find more
46:33
recent proofs that may be simpler than
46:35
the original proof all right any other
46:42
questions yeah well once it becomes a
46:53
child
46:53
oh okay so so what once a node becomes a
47:00
child then its subtree does not increase
47:03
in size well it depends on the
47:07
operations you do because you may end up
47:09
pulling it back out from the top-level
47:13
tree later when you do a remove and
47:15
eventually it could through changing
47:17
keys show up again somewhere else okay
47:20
so if it if it doesn't ever show up as
47:23
the root again then its size can't
47:26
change
47:31
what's the application the application
47:33
of the same as Fibonacci heap oh I don't
47:39
have the reduced key that's because I
47:40
looked at the max version if I change it
47:43
to the men then it becomes a decrease
47:45
key okay yeah so so so really the
47:50
question becomes what's the application
47:51
of Fibonacci heap because this performs
47:54
better than Fibonacci key okay and so in
47:59
reality you're going to get better
48:02
performance to this if you believe all
48:04
the experiments that have been done the
48:07
Fibonacci heap then becomes a
48:10
theoretical structure for which you can
48:11
prove a good bound but which doesn't
48:14
perform as well as the fibonacci heap
48:17
okay all right so we'll stop here