Q: "Just to be clear, path compression happens during a find operation AND union operations?" A: Yes! In fact, in the code implementation the union operation calls the find method which is where the path compression is done. Q: "why didn't you also compress A and C to point to E?" A: We lazily do path compression, so It only applies to the nodes which we unify.
It seems it would be better to set the new root of a union as the root of the tree with the larger height so that the resulting tree has the smallest height possible. See union(H,F) @ 4:07.
I did that setup at 4:07 intentionally to compare how beneficial path compression can be. You're correct in saying that as a heuristic you want to merge the smaller tree into the larger one. I've done imprical tests in the past and this has given me a performance boost.
Hey William, I'm kind of confused approx @5:00 when you do the union(J,G). Why are you path compressing based on the new graph? The graph has yet to merge together. I think it would make sense if the graph you are merging into can be path compressed. For example, lets say you have H as root node w/ node I pointing to H, and j pointing to I. There is another directed graph where F is pointing to E. Example 1) Suppose you call union(F,H). Suppose E points to H. Then F should still point to E but E now points to H and H having it's original children nodes. F is not apart of H and you are calling find(F) which has E as its root. Example 2) Suppose you call union(F,I). Then, path compression should happen and I, J and E is pointing to H. Also, F is pointing to E still.
Hey, just wondering why at 3:22 you wouldn’t compress all the traversed nodes when finding F to point to G instead, creating a star topology. It seems like this wouldn’t require any more work and would be much more optimal. Sorry to bring this up after so long, haha.
At 4:10. After executing Union(A,C) the 3rd instruction in right column, why did B point to C. I expected B to D instead because shouldn't it always be root of group1 to root of group2?; 5:25 "hadn't even finish all the instructions and we have reached the final state" What instructions? What final state? How can final state be reached without finishing an algorithm? Do you mean there are some useless instructions at the end of path compression that can be ignored due to some condition? Why is C and A pointing to E through D, instead of to E directly? I thought compression means all nodes to final parent in single step.
Great video! Just one doubt. I saw that people already asked why C and A are not connected to E, after compression, and you already answered, but still cant understand :(
Hi, William! Do you link some nodes like (C, D) and (E, F) (using different ways. It's just for this example or have some reason? Hi William! You link some nodes as (C, D) and (E, F) using different ways (left - > right and left < - right). A little different from the previous video. It's just for this example, or is there some special reason? Thanks, in advance!
Hi Thiago, if you're referring to the first example that's just a hypothetical setup to illustrate path compression. The actual direction in which the nodes are linked together does not matter, your union find will still work correctly. However, from experience, if you merge the smaller group into the larger group you can get a mild performance boost.
My version of union-find doesn't use this path compression method. My version makes the representative of each node union together and all nodes from the smaller group enter the larger group, setting it's representative to the representative of the larger group.
5:25 finding A or C at this point, still take more than one hop (in this case, 2 hops) since they're not directing pointing at E. Could you prove that such 2 hops in worst case? is it still constant time, or become linear time?
What if I want to increase the size of my array? Initially the array is initialized as 100 say, and I now want to add new element, how does this algorithm tackle that?
A bit late, but no. Path compression does not impose an underlying implementation data structure. You can achieve path compression using an array by modifying the stored values
www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/ I think the general case is that whenever we execute a union call, we run a find on the two arguments as well.
it's not clear at this stage what's the point of all of this - since all nodes are connected you can simply point all nodes to one - no need for "instructions". If the point was to show disjoint components then this example is awful - there is no disjoint components.
Holy mother of clarity. Great explanation, bro.
Thank you for explaining these concepts so beautifully. Please keep posting new videos. Thank you so much.
All 4 videos on this topic are a gem!
Just to be clear, path compression happens during a find operation AND union operations?
Also, why didn't you also compress A and C to point to E?
Q: "Just to be clear, path compression happens during a find operation AND union operations?"
A: Yes! In fact, in the code implementation the union operation calls the find method which is where the path compression is done.
Q: "why didn't you also compress A and C to point to E?"
A: We lazily do path compression, so It only applies to the nodes which we unify.
this comment should be pinned
It seems it would be better to set the new root of a union as the root of the tree with the larger height so that the resulting tree has the smallest height possible. See union(H,F) @ 4:07.
I did that setup at 4:07 intentionally to compare how beneficial path compression can be. You're correct in saying that as a heuristic you want to merge the smaller tree into the larger one. I've done imprical tests in the past and this has given me a performance boost.
Thank you so much it is extremely helpful. One image's worth 1000 of words
At 4:09, after Union(H, F), why H points to E? H's group is larger.
it doesn't make a difference
you can do it both ways
only condition is they should belong to the same group
In around 4:11, for operation Union(A,C), I don't understand why the result is B points to C instead of B points to D?
It could go eitherway, it does not matter as long as the components are unified.
At 3:24, should we also point A B C D E to G instead of F?
Hey William, I'm kind of confused approx @5:00 when you do the union(J,G). Why are you path compressing based on the new graph? The graph has yet to merge together. I think it would make sense if the graph you are merging into can be path compressed.
For example, lets say you have H as root node w/ node I pointing to H, and j pointing to I. There is another directed graph where F is pointing to E.
Example 1) Suppose you call union(F,H). Suppose E points to H. Then F should still point to E but E now points to H and H having it's original children nodes. F is not apart of H and you are calling find(F) which has E as its root.
Example 2) Suppose you call union(F,I). Then, path compression should happen and I, J and E is pointing to H. Also, F is pointing to E still.
Exactly!!
same doubt :v
Hey, just wondering why at 3:22 you wouldn’t compress all the traversed nodes when finding F to point to G instead, creating a star topology. It seems like this wouldn’t require any more work and would be much more optimal. Sorry to bring this up after so long, haha.
At 4:10.
After executing Union(A,C) the 3rd instruction in right column, why did B point to C. I expected B to D instead because shouldn't it always be root of group1 to root of group2?;
5:25 "hadn't even finish all the instructions and we have reached the final state"
What instructions? What final state? How can final state be reached without finishing an algorithm? Do you mean there are some useless instructions at the end of path compression that can be ignored due to some condition?
Why is C and A pointing to E through D, instead of to E directly? I thought compression means all nodes to final parent in single step.
3:22 Would you not make E, D, C, B, A parents all G?
Great video!
Just one doubt. I saw that people already asked why C and A are not connected to E, after compression, and you already answered, but still cant understand :(
at 3:27, wouldn't it have been better if everything pointed to G?
Love the way it's explained.
Hi, William! Do you link some nodes like (C, D) and (E, F) (using different ways. It's just for this example or have some reason?
Hi William! You link some nodes as (C, D) and (E, F) using different ways (left - > right and left < - right). A little different from the previous video. It's just for this example, or is there some special reason? Thanks, in advance!
Hi Thiago, if you're referring to the first example that's just a hypothetical setup to illustrate path compression. The actual direction in which the nodes are linked together does not matter, your union find will still work correctly. However, from experience, if you merge the smaller group into the larger group you can get a mild performance boost.
My version of union-find doesn't use this path compression method. My version makes the representative of each node union together and all nodes from the smaller group enter the larger group, setting it's representative to the representative of the larger group.
So you use Union Rank (aka Weighted Quick Union) together with Path compression. Which ends up with T O(1) find and union?
5:25 finding A or C at this point, still take more than one hop (in this case, 2 hops) since they're not directing pointing at E. Could you prove that such 2 hops in worst case? is it still constant time, or become linear time?
He had not enough space to represent all the nodes pointing to E around it that's why he didn't pointed A and C to it.
Savior. Thanks for this amazing content ! :)
brilliant and easily explained thhanks
Why don't we compress the whole tree after union rather than just the nodes we would like to merge while searching for their roots ?
The answer is we're compressing the whole tree is a lazy fashion. Why bother compressing nodes we're not going to use?
@@WilliamFiset-videos lazy compress :)
What if I want to increase the size of my array? Initially the array is initialized as 100 say, and I now want to add new element, how does this algorithm tackle that?
4:51 I think "compressing" J to H is not justified in vid. you are not doing Union(J,H) nor Find(J) :(
J and G have the same root, which is H. The union function calls find(j) and find(g)
Thank you! Great explanation.
Great video series
Great GREAT video!!!!!!! GREAT!!
Does path compression implies using trees as a data structure for the union find, and without compression means relying on linked lists?
A bit late, but no. Path compression does not impose an underlying implementation data structure. You can achieve path compression using an array by modifying the stored values
I have one doubt, if we do path compression, we would lose our previous root nodes, so we cannot revert them back :(
We don't need to revert back, since we never un-union
Thanks
Thank you!
hello prime's chat!
COuld have explained more clearly as to how it is compressed in each step!
thank you!!
you are genius, one of the best explanation!!!
5:10 Something that confuses me is that we are compressing the path during union command, but in your source code we compress during find() method
www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/
I think the general case is that whenever we execute a union call, we run a find on the two arguments as well.
Good
it's not clear at this stage what's the point of all of this - since all nodes are connected you can simply point all nodes to one - no need for "instructions". If the point was to show disjoint components then this example is awful - there is no disjoint components.
omg stop using purple, im color blind, cant distinguish subtle difference between blue and purple. Green would be good!!
it's a kind of bad animation. If the animation made more clear, then it is easier for beginners to understand more.