Let's think about how we might actually create an implementation of the disjoint sets algorithm. In doing so, I'm going to create the most simple algorithm that I can think of. We'll look at how well it performs and what problems that we have in the simple implementation, so we can go ahead and build a more complex implementation that solves the exact same problem, motivated by the example we see right now. So, what I'm going to do is I'm going to store all of the elements inside of my set into an array. So, let's look at an example. Here I have the element zero, one, four, two, seven, three, five, and six. Luckily, this is the numbers between zero and seven, and these are nice indices into an array. If we don't already have this nice index relationship, we can put a hash table in front of this using our hash algorithm that we learned about a few weeks ago to create an index that can be indexing into an array. So, given these elements, I can simply say at every single index into my array, the value in the array is this set identity for that particular group. So, zero is in the group that has a set identity zero. The element one is in the group that has a set identity zero. The element two is in the group that has set identity two. The element three is over here in the group has a set identity of three. The element four is in the group that has a set identity of zero. The element five, it's in the group that has the set identity of three. Elements six also in the group with a set identity of three. Finally, elements seven is the element which is in this set with the identity of two. So, notice the value in every single array is the exact identity of our structure itself. So, that means to find the identity of a given element. So, to find the identity of element four. Then we can simply look at index four in the array and find out what the set identity is for that. So, looking at element four, we know that the set identity for find a four is going to be zero. This is incredibly fast, we're just looking up into an array, we know that the running time of this is all of one time, this is an incredible running time for being able to find an array. But let's think about what happens when we need to union two things together. Suppose I want a union the element four and two together, you need four and two, means that the entirety of the left set and the middle set must be union to one same set. What that means is two and seven, needs their set identities updated to be zero. Unfortunately, in our current implementation, we have no way to know what elements are in the element two or what elements are in the set identity that has the set identity of two, so two and seven are both in the same set, but no data structure here allows us to look up what all elements have the set identity two. Instead the absolute only way to do this is to go through the array and say, hey index zero, are you part of set identity two? No. Okay. Index one are you part of it? No. Index two your part of it? Yes. Okay, awesome. Then we need to update your identity to zero. Index three, are you part of it? No. Index four, are you part of it? No. Index five? No. Six? No. Only here when we get seven, we find another element that's in our set. Here we update that to be zero to update the correct set identity. Doing that means to find every single element that's in the set that we're unioning together. Using a disjoint set, we have a find that runs in O of 1 time, it really great running time for find, but the actual running time for union means we have to traverse the entire array, it's an O of n running time which is absolutely terrible. So, what we hope to do is, we hope to actually build something that's going to be nearly as efficient find, nearly that constant time running time, but also ensure that we have an efficient running time in the actual union operation. So, what were we aiming to do in the next lecture is to use the base ideas here and actually build on it to create a more efficient algorithm to build a disjoint sets in our run time much smaller than O of n, so I'll see you there.
