Union by Rank Heuristic in Union-Find

Understanding the Union by Rank Heuristic in Union-FindAlgorithms The Union-Find algorithm is a data structure used in computer science that keeps track of the division of a set of components into a number of distinct(non-overlapping) subgroups. Two primary operations are provided by theUnion-Find algorithm: Find: identifies the subset in which a specific element is included. You can use this to determine whether two elements belong to the same subset.Union: creates a new subset by joining two existing ones.How to keep track of each subset's size (or height) is a crucial factor to take intoaccount while merging two subsets. The Union by Rank heuristic is useful inthis situation. What is the Union by Rank Heuristic? A Union-Find method can effectively combine two disjoint sets by using the Union by Rank heuristic. The fundamental concept is to always join thesmaller tree's root to the larger tree's root. By doing this, the height of theresulting tree only grows logarithmically as more elements are added to the set. This tactic is carried out by maintaining a second array named rank, where rank[i] is the height of the subtree with root i. When two trees arecombined, the roots of the smaller ranking tree are joined to the roots of thelarger ranking tree. When the ranks of two trees are equal, either tree's root canbe joined to the root of the other tree, increasing the rank of the new tree by one. The Find Operation The fundamental Find operation is comparable to the Find operation in the Union-Find algorithm with the Union by Rank heuristic. The objective is tolocate the set's root that contains a particular element. Path compression is usedin the implementation to boost performance. The Union Operation There are three primary steps to the Union operation in the Union-Find algorithm with the Union by Rank heuristic: 1) Track down the origins of the two combining elements.

2) Return if the roots are identical because the items are already in the same set.3) Connect the smaller tree's root to the larger tree's root, and if necessary,update the rank of the final tree. Example Consider the following set of elements: {1, 2, 3, 4, 5, 6}. After calling MakeSet for each element, we have the following data structure: element  parent  rank 1        1      02        2      03        3      04        4      05        5      06        6      0 Let's now dial Union (2, 4). 2 and 4 each have 2 and 4 as their roots. We attachthe root of 4 to the root of 2 and set parent[4] to 2 because rank[2] = 0 andrank[4] = 0. The final data structure is as follows: element  parent  rank 1        1      02        2      13        3      04        2      05        5      06        6      0 Next, let's call Union(1, 3). The roots of 1 and 3 are 1 and 3, respectively. Sincerank[1] = 0 and rank[3] = 0, we attach the root of 3 (3) to the root of 1 (1), andset parent[3] = 1.