并查集 rank 的优化

精华

小牛编辑

162浏览

2023-03-14

上一小节介绍了并查集基于 size 的优化，但是某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。

根据上一小节，size 的优化，元素少的集合根节点指向元素多的根节点。操完后，层数变为4，比之前增多了一层，如下图所示：

由此可知，依靠集合的 size 判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这就是基于 rank 的优化。

我们在并查集的属性中，添加 rank 数组，rank[i] 表示以 i 为根的集合所表示的树的层数。

...
private int [ ] rank ; // rank[i]表示以i为根的集合所表示的树的层数
private int [ ] parent ; // parent[i]表示第i个元素所指向的父节点
private int count ; // 数据个数
...

构造函数相应作出修改：

...
// 构造函数
public UnionFind4 ( int count ) {
rank = new int [count ] ;
parent = new int [count ] ;
this. count = count ;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for ( int i = 0 ; i < count ; i ++ ) {
parent [i ] = i ;
rank [i ] = 1 ;
}
}
...

合并两元素的时候，需要比较根节点集合的层数，整个过程是 O(h)复杂度，h为树的高度。

...
public void unionElements ( int p, int q ) {
int pRoot = find (p ) ;
int qRoot = find (q ) ;
if ( pRoot == qRoot )
return ;

if ( rank [pRoot ] < rank [qRoot ] ) {
parent [pRoot ] = qRoot ;
}
else if ( rank [qRoot ] < rank [pRoot ] ) {
parent [qRoot ] = pRoot ;
}
else { // rank[pRoot] == rank[qRoot]
parent [pRoot ] = qRoot ;
rank [qRoot ] += 1 ; // 此时, 我维护rank的值
}
}
...

Java 实例代码

UnionFind3.java 文件代码：

package union ;
/**
* 基于rank的优化
*/
public class UnionFind4 {
private int [ ] rank ; // rank[i]表示以i为根的集合所表示的树的层数
private int [ ] parent ; // parent[i]表示第i个元素所指向的父节点
private int count ; // 数据个数
// 构造函数
public UnionFind4 ( int count ) {
rank = new int [count ] ;
parent = new int [count ] ;
this. count = count ;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for ( int i = 0 ; i < count ; i ++ ) {
parent [i ] = i ;
rank [i ] = 1 ;
}
}
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find ( int p ) {
assert ( p >= 0 && p < count ) ;
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while ( p != parent [p ] )
p = parent [p ] ;
return p ;
}
// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
public boolean isConnected ( int p , int q ) {
return find (p ) == find (q ) ;
}
// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
public void unionElements ( int p, int q ) {
int pRoot = find (p ) ;
int qRoot = find (q ) ;
if ( pRoot == qRoot )
return ;
if ( rank [pRoot ] < rank [qRoot ] ) {
parent [pRoot ] = qRoot ;
}
else if ( rank [qRoot ] < rank [pRoot ] ) {
parent [qRoot ] = pRoot ;
}
else { // rank[pRoot] == rank[qRoot]
parent [pRoot ] = qRoot ;
rank [qRoot ] += 1 ; // 维护rank的值
}
}
}