Union-Find size optimization
Following the approach from the previous subsection, we take the disjoint-set as shown in the figure below and performunion(4,9)operation.
The structure after the merge operation is:
It can be seen that the tree height of this structure is relatively high. If the number of elements increases at this time, the resulting cost will be relatively large. Solving this problem is actually very simple: before performing the specific pointing operation, first judge, and point the root of the set with fewer elements to the root of the set with more elements, which can generate a tree with a lower height with higher probability.
When constructing the disjoint-set, one more parameter is needed,szarray,sz[i]indicates thatithe number of elements in the set rooted at...
public UnionFind3(int count){
parent = new int[count];
sz = new int[count];
this.count = count;
// initialize, each parent[i] points to itself, indicating that each element forms a set by itself
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
sz[i] = 1;
}
}
During the merge operation, the direction of merging is determined based on the number of elements in the trees where the two elements are located.
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
if( sz[pRoot] < sz[qRoot] ){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
After optimization, the merge result is as follows: 9 points to parent node 8.
Java example code
Source code package download:Download
UnionFind3.java file code:
/**
* Union-Find Set size optimization
*/
public class UnionFind3 {
// parent[i] represents the parent node of the i-th element
private int[] parent;
// sz[i] represents the number of elements in the set rooted at i
private int[] sz;
// number of data elements
private int count;
// constructor
public UnionFind3(int count){
parent = new int[count];
sz = new int[count];
this.count = count;
// initialize, each parent[i] points to itself, indicating that each element forms a set by itself
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
sz[i] = 1;
}
}
// find process, find the set number corresponding to element p
// O(h) complexity, h is the height of the tree
private int find(int p){
assert( p >= 0 && p < count );
// keep querying the parent node until reaching the root node
// characteristic of root node: parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// check whether element p and element q belong to the same set
// O(h) complexity, h is the height of the tree
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// merge the sets containing element p and element q
// O(h) complexity, h is the height of the tree
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// Determine the merge direction based on the number of elements in the trees where the two elements are located
// Merge the set with fewer elements into the set with more elements
if( sz[pRoot] < sz[qRoot] ){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}