java的基本数据结构,

  java的基本数据结构,

  一.概述二。实现2.1快速查找2.2快速联合3。优化3.1基于大小的优化3.2基于等级的优化3.2.1路径压缩)3.2.2路径分裂)3.2.3路径减半

  00-1010并集:一种树形数据结构,用于解决一些不相交集合的合并和查询问题。例如,如果有n个村庄,检查两个村庄之间是否有连接道路来连接两个村庄。

  两个内核:

  Find) :查找元素所在的集合。

  Union) :)将两个元素的集合合并为一个集合。

  实现00-1010并行搜索的常用方法有两种。

  查找(快速查找)

  查找的时间复杂度:O(1)合并的时间复杂度:O(n)快速并集

  (Find): O(logn)的时间复杂度可以优化到O(a(n))a(n) 5。合并的时间复杂度:O(logn)可以优化到O(a(n))a(n) 5。树结构是通过使用数组实现的,数组的下标是元素,数组中存储的值是父节点的值。

  创建抽象类Union Find

  公共抽象类union find { int[]parents;/* * *初始化联合集* @ param capacity */public union find(int capacity){ if(capacity 0){ throw new illegalargumentexception( capacity必须=0 );}//开始时,每个元素的父节点(根节点)是自己的parents=new int[capacity];for(int I=0;I家长.长度;I){ parents[I]=I;}}/* * *检查v1 v2是否属于同一个集合*/public boolean issame (intv1,int v2){ return find(v1)==find(v2);}/* * *查找V所属的集合(根节点*/public abstract int Find(int V);/* * *合并v1 v2所属的集合*/公共抽象void union (intv1,int v2);//range check public void range check(int v){ if(v 0 v parents . length)抛出new illegalargumentexception (v超出容量);}}

  00-1010快速查找实现的并集,树的最高高度为2,每个节点的父节点为根节点。

  公共类UnionFind_QF扩展了union find { public union find _ QF(int capacity){ super(capacity);}//Look up @ override public int find(int v){ range check(v);回报父母[v];}//并将v1所在的集合合并到v2所在的集合@ override public void union (intv1,int v2){//并找到v1 v2的父(根)节点int P1=find(v1);int p2=find(v2);if(p1==p2)返回;//将所有以v1的根节点为根节点的元素合并到v2所在的集合中,即将父节点改为v2的父节点for(int I=0;I家长.长度;I){ if(parents[I]==P1){ parents[I]=p2;}} }}

  

目录

 

  公共类UnionFind_QU扩展了union find { public union find _ QU(int capacity){ super(capacity);}//检查中@Overridepublic元素的根节点

  t find(int v) { //检查下标是否越界rangeCheck(v); // 一直循环查找节点的根节点while (v != parents[v]) {v = parents[v];}return v;} //V1 并到 v2 中@Overridepublic void union(int v1, int v2) {int p1 = find(v1);int p2 = find(v2);if(p1 == p2) return; //将v1 根节点 的 父节点 修改为 v2的根结点 完成合并parents[p1] = p2;}}

 

  

三、优化

并查集常用快并来实现,但是快并有时会出现树不平衡的情况

 

  

 

  有两种优化思路:rank优化,size优化 

  

 

  

3.1基于size的优化

核心思想:元素少的树 嫁接到 元素多的树

 

  

public class UniondFind_QU_S extends UnionFind{ // 创建sizes 数组记录 以元素(下标)为根结点的元素(节点)个数private int[] sizes; public UniondFind_QU_S(int capacity) {super(capacity); sizes = new int[capacity]; //初始都为 1for(int i = 0;i < sizes.length;i++) {sizes[i] = 1;}} @Overridepublic int find(int v) { rangeCheck(v); while (v != parents[v]) {v = parents[v];}return v;} @Overridepublic void union(int v1, int v2) {int p1 = find(v1);int p2 = find(v2);if(p1 == p2) return; //如果以p1为根结点的元素个数 小于 以p2为根结点的元素个数 p1并到p2上,并且更新p2为根结点的元素个数if(sizes[p1] < sizes[p2]) { parents[p1] = p2; sizes[p2] += sizes[p1]; // 反之 则p2 并到 p1 上,更新p1为根结点的元素个数}else {parents[p2] = p1;sizes[p1] += sizes[p2];}}}

基于size优化还有可能会导致树不平衡

 

  

 

  

3.2基于rank优化

核心思想:矮的树 嫁接到 高的树

 

  

public class UnionFind_QU_R extends UnionFind_QU { // 创建rank数组 ranks[i] 代表以i为根节点的树的高度 private int[] ranks; public UnionFind_QU_R(int capacity) {super(capacity); ranks = new int[capacity]; for(int i = 0;i < ranks.length;i++) {ranks[i] = 1;} } public void union(int v1, int v2) { int p1 = find(v1);int p2 = find(v2);if(p1 == p2) return; // p1 并到 p2 上 p2为根 树的高度不变if(ranks[p1] < ranks[p2]) {parents[p1] = p2; // p2 并到 p1 上 p1为根 树的高度不变} else if(ranks[p1] > ranks[p2]) {parents[p2] = p1; }else { // 高度相同 p1 并到 p2上,p2为根 树的高度+1parents[p1] = p2;ranks[p2] += 1;}}}

基于rank优化,随着Union次数的增多,树的高度依然会越来越高  导致find操作变慢

 

  有三种思路可以继续优化 :路径压缩、路径分裂、路径减半

  

 

  

3.2.1路径压缩(Path Compression )

在find时使路径上的所有节点都指向根节点,从而降低树的高度

 

  

 

  

/** * Quick Union -基于rank的优化 -路径压缩 * */public class UnionFind_QU_R_PC extends UnionFind_QU_R { public UnionFind_QU_R_PC(int capacity) {super(capacity);} @Overridepublic int find(int v) {rangeCheck(v); if(parents[v] != v) { //递归 使得从当前v 到根节点 之间的 所有节点的 父节点都改为根节点parents[v] = find(parents[v]);}return parents[v];}}

虽然能降低树的高度,但是实现成本稍高 

 

  

 

  

3.2.2路径分裂(Path Spliting)

使路径上的每个节点都指向其祖父节点

 

  

 

  

/** * Quick Union -基于rank的优化 -路径分裂 * */public class UnionFind_QU_R_PS extends UnionFind_QU_R { public UnionFind_QU_R_PS(int capacity) {super(capacity);} @Overridepublic int find(int v) {rangeCheck(v);while(v != parents[v]) { int p = parents[v];parents[v] = parents[parents[v]];v = p;}return v;}}

 

  

3.2.3路径减半(Path Halving)

使路径上每隔一个节点就指向其祖父节点

 

  

 

  

/** * Quick Union -基于rank的优化 -路径减半 * */public class UnionFind_QU_R_PH extends UnionFind_QU_R { public UnionFind_QU_R_PH(int capacity) {super(capacity);} public int find(int v) { rangeCheck(v); while(v != parents[v]) {parents[v] = parents[parents[v]];v = parents[v];}return v;} }

使用Quick Union + 基于rank的优化 + 路径分裂 或 路径减半

 

  可以保证每个操作的均摊时间复杂度为O(a(n)) , a(n) < 5

  到此这篇关于java 数据结构并查集详解的文章就介绍到这了,更多相关java 并查集内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT!

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

相关文章阅读

  • mysql复合索引和组合索引,mysql组合索引数据结构
  • mysql复合索引和组合索引,mysql组合索引数据结构,Mysql之组合索引方法详解
  • mysql复合索引和组合索引,mysql复合索引数据结构
  • mysql复合索引和组合索引,mysql复合索引数据结构,MySQL的复合索引总结
  • b+树 多路搜索树,数据结构中树的分类
  • b+树 多路搜索树,数据结构中树的分类,数据结构-树(三):多路搜索树B树、B+树
  • avl树的构造,avl树特性,数据结构之AVL树详解
  • 数据结构c语言哈夫曼树,c语言哈夫曼树的构造,使用C语言详解霍夫曼树数据结构
  • c语言数据结构算法编程库,数据结构 c语言中文网
  • c语言数据结构算法编程库,数据结构 c语言中文网,C语言编程数据结构基础详解小白篇
  • c++纸牌游戏,数据结构纸牌游戏c语言
  • c++纸牌游戏,数据结构纸牌游戏c语言,C语言实战之纸牌游戏
  • ,,c#解析jobject的数据结构
  • ,,javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】
  • ,,Java 数据结构与算法系列精讲之背包问题
  • 留言与评论(共有 条评论)
       
    验证码: