Alright, time to talk about the union find, also sometimes called the disjoint set. This is my favorite data structure. So let's get started. So an outline of things we'll be covering about the union find. First I'll be going over a motivating example magnets. Just to illustrate how useful the union find can be.

Then we'll go over a classic example of an algorithm which uses the union find specifically crystals, a minimum spanning tree algorithm, which is very elegant, and you'll see why it needs the union find to get the complexity it has. Then we're going to go into some detail concerning the find in the Union operations, the two core operations that you can find uses. And finally we'll have a look at path compression. What gives us the really nice amortized constant time The unifying provides Ok, let's dive into some discussion examples concerning the union find. So, what what is the union fine. So, the union finds the data structure that tracks elements which are split into one or more disjoint sets and the unified has two primary operations, find an union.

What find does is given an element, the union find will tell you what group that element belongs to. And union emerges two groups together. So if we have this example with magnets, suppose all these gray rectangles you see on the screen are magnets, and also suppose that the magnets have a very high attraction to each other, meaning they want to merge together to form some sort of configuration. So, if I label all the magnets and give them numbers, and we start merging, the magnets have the highest attraction. First, we're going to merge six and eight together since the closest. So in our union find, we would say union six, and eight.

And when we do a look up on to find out which groups six and eight belong to, they will belong to the blue group. Now, perhaps two, three and three and four are highly attracted to each other, so they would form a group. So they would form the yellow group. And perhaps 1013 and 14 would also form a group. And this keeps on going and we unify magnets into groups. And perhaps we merge some magnets onto already existing groups.

So we unify Grey magnets, which is just a magnet in its own group, and the to an already existing group, but also we can unify groups of magnets which are different colors. And then we assign it an arbitrary color. So blue, so suddenly everything in the yellow group went into the blue group. And now when we would do a look up in our union find to determine which group say 234. Now we'd say, Ah, you're in the blue group. And the unifying does all this merging and finding in a very efficient manner, which is why it's so handy to have around not explained currently how that works.

We'll get into that in the later video. This is just a motivating example. So where are other places that the union find is used? Well We will. Well, we see the unifying again in crystals minimum spanning tree algorithm. In another problem called grid percolation where there's a bunch of dots on a grid, and we're trying to see if there's a path from the bottom of the grid to the top of the grid or vice versa, then the union find lets us do that efficiently by merging together paths.

Also, similar kind of problem in network connectivity are two vertices in the graph connected to each other through a series of edges. And also perhaps in some more advanced examples, like the least common ancestor in a tree, and also in image processing. So what kind of complexity can we attribute to the union find? The complexity is excellent. So its construction is linear time, which isn't actually bad at all. Then the You find, get component and check if connected operations all happened in what's called amortized constant time.

So almost constant time, although not quite constant time. And finally, count components. Well, we can determine how many components are in our magnet examples, how many different groups of nine that we have. And we can do that in constant time, which is really, really great. So in the next video, we're going to have a look at crystals minimum spanning tree algorithm and how it uses the union find. So guys, thank you for watching and I will catch you then.