Analysis (Optional)

Loading...

Do curso por University of California San Diego

Data Structures

1463 classificações

University of California San Diego

Data Structures

1463 classificações

Curso 2 de 6 em Specialization Data Structures and Algorithms

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!

Na lição

Priority Queues and Disjoint Sets

We start this module by considering priority queues which are used to efficiently schedule jobs, either in the context of a computer operating system or in real life, to sort huge files, which is the most important building block for any Big Data processing algorithm, and to efficiently compute shortest paths in graphs, which is a topic we will cover in our next course. For this reason, priority queues have built-in implementations in many programming languages, including C++, Java, and Python. We will see that these implementations are based on a beautiful idea of storing a complete binary tree in an array that allows to implement all priority queue methods in just few lines of code. We will then switch to disjoint sets data structure that is used, for example, in dynamic graph connectivity and image processing. We will see again how simple and natural ideas lead to an implementation that is both easy to code and very efficient. By completing this module, you will be able to implement both these data structures efficiently from scratch.

Trees for Disjoint Sets7:54

Union by Rank9:41

Path Compression6:07

Analysis (Optional)18:17

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Our goal in this video is to show that if we use both path compression and

union by rank heuristics then the average running time of a single operation

is upper bounded by big O of log star of N.

Before going into the details of the proof,

let's realize a few important facts.

First of all, know that since we are now using path compression,

it is no longer the case that the rank of

node i is equal to height of the tree rooted at vertex i.

However, it is still true that the rank is an upper bound.

On the corresponding height.

Let me illustrate this with a toy example.

So, I assume that we have a tree like this.

So, this is root say vertex 5.

Here we have vertex 2 and

we have node 3, node say 6.

Assume that currently rank of this node is 2 say 0, this is 1 and this also 0.

We now recall find of 6.

This will re-attach 6 to the current root of this tree.

So what we get is the following,

5, 3, 1.

And also 6 now stays here, all right?

So we see that the height of these three is equal to 1.

However the rank of the root is still equal to 2.

Recall that find doesn't use and doesn't change any rank values.

Also for this node 3, it's height.

The height of the tree rooted at element 3 is equal to 0,

however the rank is equal to 1.

Well, intuitively it is clear path compression can only decrease the height.

So for this reason, rank is no longer equal

to the height of the corresponding tree however the height is at most the length.

Okay.

Another important thing is the following.

It is still true that for any root node i of rank k.

The corresponding sub 3 contains at least 2 to the k elements.

And this can be seen by realizing that the past compression does not affect

any root nodes.

I mean, if we have a root node whose height is k,

then no matter how many times and for which nodes in these sub tree

we call find with path compression, all this nodes are still in

this subtree rooted at this nodes exactly because this node is a root.

So any node from this subtree cannot be attached

to some other vertex and some other subtree.

This node is still, so once again if we have a node who is still a root and

whose rank is k, then the corresponding subtree contains at least 2 to

the k elements, 2 to the k nodes.

On this slide we discuss a few more important properties.

The first one of them says that we have,

in our forest, at most n divided by 2 to the k nodes of rank k.

Why is that?

Well, recall that if we create a new node of rank k

then it was created by merging two nodes of rank k-1.

Okay.

So we know that currently this node is a root.

At the same time,

we know that the correspondence subtree contains at least 2 to the k nodes.

If we have another another node of rank k.

Then it also contains at least 2 to the k nodes.

Which means that if we have too many such nodes.

I mean, too many nodes of rank k.

By saying too many, I mean that its number is greater than n divided by 2 to the k.

Then overall, we have more than n element.

Which is a contradiction, right?

The second property is that, when we go up,

the rank strictly increases.

Well, this was clear if we do not use past compression.

I mean, if rank is equal to the height of the corresponding subtree,

then this is completely clear.

Let me recall that if we have for example a tree

of height two, then the height of this tree is two.

The height of this subtree is one.

The height of this subtree is zero.

Let's say this is element 5.

This is 4.

This is 8.

Now we have passed compression,

so we need to check what happens when we compress some paths.

If we call Find(5), for example, then we'll be reattached to the current root.

But it will still be 2.

That the rank of the parent.

So let me fix this.

This is node 8.

The rank of the parent is strictly

greater than the rank of a child.

The last property is, says that when a node

becomes an internal node it will be an internal node forever, right.

It will not have a chance to become a root and this is just because

the find operation doesn't change any roots in our forest.

While union operation takes two roots and

makes one of them a child of the other one.

So it takes two roots and leaves only one root.

Okay.

So once again when a vertex becomes an internal vertex,

a non root vertex, it will be a non root vertex forever.

We now start to estimate the running time of M operations.

First of all note that the union operation

boils down to T(all calls to FInd) operation.

And also to some constant operations.

Namely, when we have two roots that were found by two calls to.

To find that operation,

we need to hank one of them below other one which is a constant operation.

We just need to change one parent.

And also possibly we need to change the rank value.

Okay.

So for this reason when estimating the total running time we will just assume

that we have m calls to find operation.

Paths node that each Find operation traverses some

pass from a note to find the root of the corresponding tree.

So we traverse some number of edges.

So the total run in time of all the defind operations,

of all the calls to defind operation is just the total number of edges traversed.

So this is what is written here, we just need to count the number

of edges from parent a node i through it's paring j,

at traverse you know these codes.

For technical reasons we will split this number into three terms.

In the first term we will account all the edges that

lead from a vertex to the node to the root of the corresponding tree.

So the first term includes all the edges that lead from

a node to another node, which is the root in this case.

The second term include all the remaining edges where we go from i to j.

Such as there log* of rank of

a is strictly smaller than log* of rank of j, okay?

And their remaining term accounts for everything else,

namely for all the edges where we go from i to j such that j is not the root.

And that log*(rank[i]) = log*(rank[j])).

We're going to show separately for each of these terms that it

is upper bounded by big 0 of m multiplied by log star of m.

Let me show this on a small example as usual.

Assumes that we have such a path that we're going to traverse.

A path from the node at the bottom to the root of the corresponding tree.

So the numbers shown here indicate the ranks of the corresponding nodes.

Then these two nodes, these two edges will be accounted in the first term.

Just because these two nodes lead from a node to the root this thread just lead

from a node to the root of the corresponding tree.

Well, this edge for example will be accounted in the last

term because the rank of this node is 17 and

the rank of this node is 21.

And log star of this numbers are equal.

At the same time, here we have 14 the rank 14, and here we have rank 17.

And the log star of these two numbers are different.

For this reason this hatch will be accounted in the second term, okay?

So on the next sequence of slides,

we are going to estimate separately each of these three terms.

And for each of them, we are going to show that it is at most big O of m

multiplied by log* of m.

The first term is easy to estimate.

Recall that in this term we account for all the edges traversed by find operation.

Where we go from node i to its parent j such that j is the root.

Clearly for each call to find the operation

there are at most two side edges, right?

Which means that we have an upper bound big O of m.

In the second term, we need to estimate that a long number of edges traversed

it during all m calls to the find operation.

Such that we go from node i to its parent j such that j is not the root and

also log star of rank of i is strictly less than log star of rank of j.

We're going to prove here that it is upper bounded by big O of

m multiplied by log star of n.

And this is just because, when we go up from some node to

the root of the corresponding tree, the rank always increases.

However, the rank of the root is at most log n, which means that during one call

to find procedure the lock star of rank can only increase log star of n times.

Okay.

This is just because we've had an upper bound for the rank of the root.

It is upper bounded by log m which means that there

are only log star of m different possibilities for

log star of rank of folds and nodes on this.

Which means, that these can only increase, at most, log star of m times.

And we have at most, m calls to find the operations.

Which gives us, an upper bound m, to get, m multiplied by log star of m.

Now it remains to estimate the last term.

Where we account for

all the address traversed during m calls to the find operations.

Where we go from node i to node j through its parent j such that j is not the root,

first of all.

And then the rank, the log star of rank of i is equal to log star of n of j.

What we're going to show is that the total number of side edges

is upper bounded by big O of m multiplied by log star of m.

Note that this is even better than what we need.

What we need is a recap upper bound which is m log star of n.

Recall that we know that m is greater than m just because m is the total number

of operations, while n is the number of calls to make said operations.

To estimate the required term, consider a particular node i and assume for

completeness that it's rank lies in an interval from k plus one to two to the k.

Recall that this was the form of interval

through which the lock star function is fixed.

Okay?

Now let's compute the total number of nodes whose rank lies in section interval.

So we know that the total number of nodes whose rank

is equal to k plus one is at most n divided by two, to the k plus one.

So total number of nodes was ranked equal to k plus two is at most n divided by two,

to k plus two.

And so on, so the total number of nodes whose rank lies in this

interval is at most n divided by two to the k.

Okay. The next stop equation is that each time

when we call Find of i, it is adopted by a new parent and since it is new.

So, at this point we know that if we have a node i and its parent j is not the root.

Yes, this is essential.

Which means that when we go up we find another root when we cofind a Find of i.

And at this point we will reattach node i to this new root.

And this new root has strictly larger rank.

And this in turn means that after most 2 to the k calls to find of i.

Find(i) will be adopted by a new parent

whose rank, for sure, does not lie in this interval.

Just because the rank of this interval is at most 2 to the k.

So if we increase the rank of the parent of i,

at least 2 to the k times, it will be greater than 2 to the k for sure.

Right.

We now have everything to conclude this proof.

To conclude estimating the required term.

Recall that we are estimating the total number of address traversed

during n calls to client.

Where we go from a node i to its parent j,

such that log star of rank of a is equal to log star of rank of j.

So we have just proved that there are at most n divided by 2 to the k nodes

whose rank lies in the interval from k plus 1 to 2 to the k.

We then explained why Any such node whose rank lies in such an interval,

contributes, at most, 2 to the k to the term that we are currently estimating.

This means that just all the nodes from, whose rank lies in such an interval.

Contributes, at most big O of N to this term, right?

Now it remains to note that the total number of different intervals

is at most log star of n.

Which means that the total contribution of all such nodes i to the estimated

term is at most big O of n Multiplied by log star of n.

We now conclude the whole lesson.

So in this lesson we considered it an implementation of the joins of

data structure where each set is represented by a tree.

And for this reason we have a forest of trees.

The ID of each set is just the root of the corresponding tree.

We then consider it to heuristics.

The first one is called Union by rank.

It says that when merging two trees, it makes sense to attach

a shorter one to the root of a taller one, okay?

This helps to keep trees in our forest shallow.

And for this we keep the rank of each subtree rooted

at a particular node in a separate array called rank.

We then discussed another heuristic which is called Path compression.

The idea is the following.

When we traversed a path from a node to the root of the corresponding tree,

we may want to reattach all the nodes found on this path directly to the root.

Because this potentially will save us time for further find operations, right.

We then proved that the resulting implementation turns out

to be extremely efficient,

namely the amortized running time of each operation is big O of log star of n.

And log star of n is an extremely slowly growing function.

In particular, log* n is at most five for all practical values of n.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play