An introduction to the disjoint set data structure, including arbitrary unions, union by size, and union by height.
Generating Random Mazes - • Creating Random Mazes ...
Kruskal's Algorithm for Finding Minimum Spanning Trees - • Kruskal's Algorithm fo...
Timestamps
------------------------------------------------
0:00​ - What we use Disjoint Sets for
0:38 - Important Assumptions
1:01​ - Basic Idea to Implement a Disjoint Set
1:54​ - Find Operation
2:14 - Example: Finding the Set Label for an Item
3:17​ - Union Operation
3:55​ - Example: Unioning Two Sets (Arbitrary)
4:24​ - Importance of Set Roots in Unions
5:38​ - Problem with Arbitrary Unions
6:26​ - Solving the Arbitrary Union Problem (With different Unions)
7:03​ - Solution: Union By Size
7:56​ - Example: Union By Size
9:44​ - Evaluation: Union By Size
10:26 - Solution: Union By Height
11:20 - Example: Union By Height
13:03 - Evaluation: Union By Height