Union Find - Union and Find Operations
ฝัง
- เผยแพร่เมื่อ 5 ก.ค. 2024
- Learn about the Disjoint Set (Union Find) union and find operations.
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/williamfiset/algor...
====================================
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 ===================================
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
I found myself losing track of his train of thoughts or mid sentence sometimes, playing this at 1.5 speed really helped me understand it better!
Man you are so underrated, you create amazing videos with concise explaination.
this is literally saving my life and WAY easier to understand than the class I'm taking lol. thank you!!
Do you have education loan to repay?
Seriously, youtube educators save our lives.
all your videos are really helpful. thank you so much.
Thanks man, just by listening to you and listening to you and seeing the illustration it kind of nailed the point to me, that union-find is pretty much just a generalization of grouping. Not necessarily "grouping" as some specific algorithm, but any problem that you come across which can be solved by grouping elements together like Kruskal's MST
these videos are really phenomenal I appreciate it!
Very nice concept of implementation of kruskal using union-find
Awesome channel! So easy to understand!
Thanks for making this video. It was very helpful!
It pains me to see good videos like this are hidden in the algorithm while shitty videos with no efforts have so many views. Keep up the good work william.
good video, 1.25 speed makes it perfect.
More like 2.0 :D
@@uzeyirveli yess
@@user-rf4vc7mt4d man you are dope please keep commenting on videos
love your username lol@@user-rf4vc7mt4d
Hey, you went to my University! Awesome work!
Very descriptive. Thank you!
Path compression is what makes Union Find an absolute *BEAST* of a Data Structure xD
I love your videos a lot. Thanks
Great video!! Thank you:)
Great video, thank you so much!
we also have to keep track of how big the subtrees are right? the array structure we have is only keeping track of vertices? unless otherwise for every iteration we count how many elements have that same root node value which would be O(n)? But we can make it O(1)?
Classes are hell; this is much easier, thank you.
Hey. What would happen in 5:22 if we had to union Node A with Node K? Would we attach J to C or J to K? As far as i understood we check which Union has more elements, and then attach the root node of the Union with less Elements to the Node we want to union it with.
great videos man !
Beautiful!
great explanation
thank you so much🥰🥰
would it be also valid if I use hashmaps and hashsets instead?
map: {
a: {}
b: {}
....
}
merge(a, b) {
combined = new Set(map.[a], map.[b])
map[a] = combined
map[b] = combined
}
find(a) {
return map[a]
}
Thank for the nice video and concise understandable explanation.
I am still wondering why we merge it as child of the root, instead child of the node as per the unify instructions
you want to unify to the root to create the smallest depth of steps from root to leaf. same concept as when you unify two different sized groups, you unify the smaller group to the larger.
path compression is a technique, that William isn't using here, that will actually reduce the depth of all groups to 2. the root and the child.
Epic Video :)
Thanks
im confused where those instructions came from. I think you made those up right? What would be an applicable problem to replace these instructions?
At 5:44 he said that because the orange component has more elements than the green component, how would the program know that when we're just performing Union(C,A), we would have to iterate through both subsets?
what if there are three nodes in group orange and in group green and we try union operation of union (orange, green) .... do we arbitrarily choose the group for the root node ?
blazzy95 The choice of the successor root node is arbitrary. Generally I merge the smaller group into the larger one but this does not affect functionality
In the case of two components having same amount of elements and being asked to merge which way is the arrow going to point ? Thanks,
you can arbitrarily choose either one and merge it in as the child of the other tree/component.
Hey William... Thanks for making and sharing such nice videos on DS and Algorithm. Do you have slack channel or Discord Server where we can connect with you and discuss on these topics directly ?
Maybe I'm missing something but at 3:44 we are grouping the elements and shouldn't there be a pattern to who becomes who's parent ex. the lower ID becomes the parent or the first element that we pass to the function is the parent? Because first two examples are (C,K) = (4,9) = 4 is parent (lower id ), second example (F, E) = (0,1) = 0 is parent ( lower id ), and then in the third one (A, J) = (5, 6) = 6 is parent? I know this is not the point of the video but shouldn't it follow the same logic if there's any? Later on it makes sense that we are merging the smaller component into the bigger one to flatten the tree. Great video overall didn't mean to be a party pooper :P
same problem for me the same logic shoould be used throughout in my opinion
yeah, you are correct, william is not following any strict pattern here .. when doing it with code you would probably always take either the smaller or bigger id in those cases (merging two nodes pointing to themselves) .. but the good point of william not following a strict pattern here is that it shows that it does not matter which id you take so maybe it is even intentional :)
@@timgoppelsroeder121 I agree with both of you.
from 5:27 could we merge the orange component to the green component?
to be more precise, Node C points to J. Here J become parent of C
can we do that ? If not, please tell why ?
@Patrick Watts number of hops ? I don't get it :/
Good day!
In the remarks session, @10:15 => it says that in the current implementation, there is 5 hops to find out whether roots of two components are same or not.
However, in the array-based implementation, every value of indexes point right to the root node. So, isnt it always 1 hop for each?
Maybe I'm missing something. Sry for this
> every value of indexes point right to the root node
example from the video does not use path compression (and you can verify that there are 5 hoops by looking on array - 7:40)
does every node track the size of its tail?
This question might be really dumb but how do I do the mapping (object to number)? Thanks for the help and for the awesome video!
array
Just use a hashmap
🎯 Key points for quick navigation:
00:01 *🔑 Explains the union and find operations in a union-find data structure.*
00:17 *📝 Creates a bijective mapping between objects and integers to construct an array-based union-find.*
01:05 *🗃️ Stores the mappings in a hash table for efficient lookup.*
01:34 *📐 Initially, each node in the array points to itself as a root node.*
02:30 *🔗 To unify objects, the smaller component's root node is set as the parent of the larger component's root node.*
04:34 *🧰 Explains the process of merging smaller components into larger ones during unification.*
06:24 *🌳 If two objects belong to the same component, no unification is needed.*
07:42 *🔍 To find the component an element belongs to, follow the parent nodes until reaching the root node.*
08:41 *🚩 The number of components equals the number of remaining root nodes and never increases.*
09:48 *⚡ Path compression, covered in the next video, improves the time complexity of union-find operations.*
Made with HARPA AI
This is just a weighted union find right?
To people like me, who didn't read the description- watch his first video first: th-cam.com/video/0jNmHPfA_yE/w-d-xo.html
Not quite sure why K is child of C, but F is child E. According to first approach - E should be a child of F
Your description has self-loop to the same video.
Shoulda used union find lol
in min 3.55, I think E should = 1
My first thought was that E should be 1 too. Then i watched video twice, he randomly defined parent in each union :)
Great video, but I didn't understand the remarks :/
More precisely the statements:
"we would have to update all the children of a node" and "the number of components is equal to the number of roots remaining"
is it ok if you are not being consistent?
ChavoTV yes, union is commutative. You should however map the smaller to the larger component due to the run time of the find operation.
x1.5
I'm mystified now
code samples would be more helpful than just diagrams
bro, can you literally make it ANYMORE boring? I doubt it... -_-
wow ruuude. it's literally an informational video and the material is really well explained. i don't think it's boring
Well "bro" what are you doing here?.... this is supposed to help you with studying... first priority wasnt for you to giggle like a little girl behind your laptop screen....... Nonetheless i hope you find topic matter more accomodating to your needs (TIP: Keeping up with the kardashians, moonshiners etc. are prime sources of entertainment for your ilk)
Thanks