Union Find Introduction

all right 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 with magnets uh just to illustrate how useful the union find can be then we'll go over a classic example of an algorithm which uses the and find specifically crucial's 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 and the union operations the two core operations the union find uses and finally we'll have a look at path compression um what gives us the really nice amortized constant time uh the union fine provides okay let's dive into uh some discussion examples concerning the union find so what what is a union find so the union find is a data structure that tracks Elements which are split into one or more uh disjoint sets and the union find has two primary operations find and Union what find does is given an element the union finds will tell you what group that element belongs to and Union merges to 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 of the highest attraction first we're going to merge six and8 together since they're the closest so in our Union find we would say Union 6 and 8 and when we do a lookup on to find out which groups six and8 belong to they would belong to the blue group uh 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 10 13 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 uh unify um a gray magnet which is just a magnet in its own group to an already existing group but also we can unify uh groups of magnets which are different colors and then we assign it an arbitrary color so uh blue so suddenly everything in the yellow group went into uh the blue group and now when we would do a look up in our Union find to determine which group uh say two three or four are now we would say ah you're in the blue group and the union fine does all this merging and finding in a very efficient manner which is why it's so handy to have around I'm not explaining 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 we well we see the union find again in cul's minimum spanning tree algorithm um in another problem called grid percolation where there's a bunch of uh 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 uh merging together paths also uh s similar kind of problem in network connectivity are two vertices and a 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 uh the complexity is excellent so its construction is linear time which isn't actually bad at all then the union 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 uh count components well we can determine how many components or in our magnet examples how many different groups of magnets 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 kill's minimum spending tree algorithm and how it uses the union find so guys thank you for watching and I will catch you then