Union Find Path Compression
ฝัง
- เผยแพร่เมื่อ 2 ต.ค. 2024
- Related Videos:
Union find intro: • Union Find Introduction
Union find kruskal's algorithm: • Union Find Kruskal's A...
Union find union and find: • Union Find - Union and...
Union find path compression: • Union Find Path Compre...
Union find code: • Union Find Code
Data Structures Source Code:
github.com/wil...
My website: www.williamfise... ===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Thank you for explaining these concepts so beautifully. Please keep posting new videos. Thank you so much.
Holy mother of clarity. Great explanation, bro.
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
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)
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 :(
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 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
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.
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.
Thank you! Great explanation.
at 3:27, wouldn't it have been better if everything pointed to G?
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.
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.
COuld have explained more clearly as to how it is compressed in each step!
3:22 Would you not make E, D, C, B, A parents all G?
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.
Thank you!
Thank you so much it is extremely helpful. One image's worth 1000 of words
So you use Union Rank (aka Weighted Quick Union) together with Path compression. Which ends up with T O(1) find and union?
Great GREAT video!!!!!!! GREAT!!
At 3:24, should we also point A B C D E to G instead of F?
hello prime's chat!
Savior. Thanks for this amazing content ! :)
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?
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 :)
Thanks
brilliant and easily explained thhanks
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
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
Love the way it's explained.
Great video series
All 4 videos on this topic are a gem!
Good
thank you!!
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.
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.
you are genius, one of the best explanation!!!
it's a kind of bad animation. If the animation made more clear, then it is easier for beginners to understand more.
omg stop using purple, im color blind, cant distinguish subtle difference between blue and purple. Green would be good!!