企业网站建设对网络营销的影响,如何选择合适的建站公司,用什么软件做网站最好,淘宝运营目录 并查集 rank 的优化
Java 实例代码
UnionFind3.java 文件代码#xff1a; 并查集 rank 的优化
上一小节介绍了并查集基于 size 的优化#xff0c;但是某些场景下#xff0c;也会存在某些问题#xff0c;如下图所示#xff0c;操作 union(4,2)。 根据上一小节…目录 并查集 rank 的优化
Java 实例代码
UnionFind3.java 文件代码 并查集 rank 的优化
上一小节介绍了并查集基于 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的值 } } }
