并查集结构

并查集特点

• 对于使用并查集构建的结构，可以使得查询两个元素是否在同一集合，以及合并集合的操作无限接近O(1)

构建过程

查找两个元素是否是同一集合

• 并查集结构会让每个元素合并后，挂在一个领头元素上，可能呈现下面的结构，要判断d和f是否是同一集合，就判断顶部的零头元素是否一样，因为a和e不一样，所以不是同一集合

优化查找领头元素

• 如上图的结构，当要查找d的领头元素时，需要一直往上遍历，当节点深度很深时，也会带来负担
• 优化方式是，当某个元素查找到领头元素后，将元素路径上所经过的所有节点的领头元素设置成查找的节点，比如d查找到a后，将b的领头元素设置成a
• 通过上面的优化手段可以看出，当使用并查集查询查询领头元素的次数越多，查找的效率就越好

设置两个元素为同一集合

• 将两个元素的领头元素设置成同一个即可，即将挂载节点少的领头元素挂载到挂载节点多的领头元素下，比如上图将e挂载到a下，因为查找元素是否在同一集合是根据领头元素是否相同来的

构建结构

class Element {value;constructor(value) {this.value = value;}
}class Union {// 给定元素对应的修饰对象elementMap;// 元素对应的父元素fatherMap;// 领头元素下挂载的元素个数sizeMap;constructor(list) {this.elementMap = new Map();this.fatherMap = new Map();this.sizeMap = new Map();list.forEach((value) => {const element = new Element(value);this.elementMap.set(value, element);// 初始将所有元素都领头元素设置成自身this.fatherMap.set(element, element);// 初始所有领头元素下挂载的元素个数为1this.sizeMap.set(element, 1);});}// 查找领头元素findHead(element) {const path = [];// 找到领头元素while (element !== this.fatherMap.get(element)) {path.push(element);element = this.fatherMap.get(element);}// 优化操作：将路径上的元素的父元素，都更新成领头元素while (path.length) {this.fatherMap.set(path.pop(), element);}return element;}// 判断是否同一集合isSameSet(value1, value2) {if (this.elementMap.has(value1) && this.elementMap.has(value2)) {return (this.findHead(this.elementMap.get(value1)) ===this.findHead(this.elementMap.get(value2)));}return false;}// 设置两个元素为同一集合setUnion(value1, value2) {if (this.elementMap.has(value1) && this.elementMap.has(value2)) {const head1 = this.findHead(this.elementMap.get(value1));const head2 = this.findHead(this.elementMap.get(value2));if (head1 !== head2) {const bigOne =this.sizeMap(head1) > this.sizeMap(head2) ? head1 : head2;const smallOne = bigOne === head1 ? head2 : head1;this.fatherMap.set(smallOne, bigOne);this.sizeMap.set(bigOne,this.sizeMap.get(bigOne) + this.sizeMap.get(smallOne));this.sizeMap.delete(smallOne);}}}
}

应用场景

并行计算集合问题

初始问题和解法

通过多线程计算，将整个内容分成左右两个区域，通过多线程分别求出左右两个面积的岛屿数量为：1个和2个，总和为3，但实际岛屿答案为2个，所以还要计算左右两个是否有岛屿是属于同一个集合

• 首先判断每一行分割的位置左右相邻节点是否都为1，是1说明为同一集合，通过并查集设置为同一集合，将总岛屿数量-1，同理后续相邻1节点只需要先通过并查集结构判断是否在同一集合，如果没有则设置为同一集合，然后岛屿数量-1的操作即可
• 因为查询和合并的代价都很低，所以再通过多线程带来的提速更快了