现在的位置: 首页 > 面试题 > 正文

并查集 rank 的优化

2022年01月10日 面试题 ⁄ 共 1845字 ⁄ 字号 暂无评论
博客主机

上一小节介绍了并查集基于 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 实例代码

源码包下载:Download

 

UnionFind3.java 文件代码:

package runoob.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的值

}

}

}

Wopus问答

Wopus问答

给我留言

留言无头像?


×