概述
并查集(Disjoint set或者Union-find set)是一种树型的数据结构(一定要一次性给定数据源,不支持流的处理),常用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。
基本操作
- 可查询两条数据是否存在于同一个集合。
- 可合并两条数据(任意节点,而不是标准节点)所在集合。
(1)合并集合
合并过程.png首先,每个节点由一个size和一对键值对组成(key是我们的data,value是对应的父级,开始父级都是自己)有犹豫key和value是不是非要使用包装对象呢?还是基本类型也可以? 根据内部实现的结构
合并的过程,举了一个实际的例子。2和1合并,先各自向上找各自树的标志节点即根节点,接着根据标志节点的size将小的树连在大的树的标志节点上,最后更改合并后标志节点的size为合并后的值。为什么标志节点的size可以代表这棵树? 因为这棵树也是合并来的,刚开始大家都是孑然一身。
(2)判断是否在同一集合
这个过程相对比较清晰。查2和1是否同源,两个节点分别向上查找自己的标志节点,相同即同源。
优化
按照上面的操作有时就会出现一些‘比较深的’树,查找这些枝干上的节点比其他的要费力许多。自己有点怀疑就举例一次合并的过程。
优化的方案:在查找某条数据的标志节点时,查找完将路径上经过的所有节点改为标志节点的直接子节点。
由于查找标志节点在合并和查同源的操作中都有用到,可以有效的避免上面的结构出现。即使不巧就是出现了,不巧还需要走最深的枝干,那么走一次,或者查过路径上的其他节点就可以使下一次变的省力。
这样的结构有什么作用呢?在查找和合并的次数逼近或超过数据量O(n)时,单次操作的时间复杂度约为O(1)常数级。
上code
实现上可以按构造树(用指针关联)的思路,操作上较为繁琐,而且对于JavaScript不查引用的基本类型数据需要使用包装对象。
我采用Map结构(实现Map可以数组、对象模拟,直接用ES6偷个懒),操作便捷,查表的过程有效避免引用类型的问题。
class Node{
constructor(str){
}
}
class UnionFindSet{
constructor(NodeList){
this.fatherMap = new Map();
this.sizeMap = new Map();
for( Node in NodeList){
this.fatherMap.set(Node, Node);
this.sizeMap.set(Node, 1);
}
}
findHead(node){
let father = this.fatherMap.get(node);
if(father && father !== node){
father = this.findHead(father);
}
this.fatherMap.set(node, father);
return father;
}
isSameSet(a, b){
return this.findHead(a) === this.findHead(b);
}
union(a, b){
if(!a || !b){
return;
}
let aHead = this.findHead(a),
bHead = this.findHead(b);
if(aHead !== bHead){
let aSize = this.sizeMap.get(aHead),
bSize = this.sizeMap.get(bHead);
if(aSize > bSize){
this.fatherMap.set(bHead, aHead);
this.sizeMap.set(aHead, aSize + bSize);
} else {
this.fatherMap.set(aHead, bHead);
this.sizeMap.set(bHead, aSize + bSize);
}
}
}
}
Node是给出的包装对象,内部可以自己设计,装什么类型的数据,不用Node直接传入基本类型的数组也可以。
网友评论