# 集合与运算

# 并查集

主要作用：

多个集合合并
查询某个元素所属集合

存储方式：

树结构：每个集合中取出一个元素作为父节点，其他元素指向父节点构成集合。
数组方式：以数组方式存储一个集合元素结构，集合元素有个属性指向父节点的数组下标。父节点下标为-1

// 数组存储方式每个集合元素的数据结构
class SetType {
  construtor() {
    // 存储集合数据
    this.data = null;

    // 指向父节点的数组所在下标。
    this.parent = -1;
  }
}

settype

# 相关操作方法

# 查找每个元素所在的集合，返回所在集合根节点索引

// 集合元素结构
class SetType {
  construtor() {
    // 存储集合数据
    this.data = null;

    // 指向父节点的数组所在下标。
    this.parent = -1;
  }
}

// settypes 存储了所有集合的元素
function Find(settypes, x) {
  let i;
  // 查找元素下标位置
  for (i = 0; i < settypes.length && settypes[i].data != x; i++);
  // 没找到
  if (i >= settypes.length) return -1;
  // 查找根节点
  for (; settype[i].parent >= 0; i = settype[i].parent);
  return i;
}

# 集合并运算

根据两个集合元素，将他们所属集合进行并运算合并成一个大集合。

思路：各自找出两个集合的根节点，将其中一个根节点父索引指向另一个集合根节点即可。

// settypes存储了所有集合的元素
function union(settypes, x1, x2) {
  let root1, root2;
  root1 = Find(settypes, x1);
  root2 = Find(settypes, x2);
  if (root1 !== root2) settypes[root2].parent = root1;
}

问题：如果多个集合一直往另一个集合进行并集处理，会导致这个集合树高度增大。元素查找根节点效率会变低。

解决方法：尽量将集合元素小的并到集合元素大的里面。

技巧

根节点 parent 为-1，可以改成根节点用负数存储集合的元素大小，这样通过根节点 parent 绝对值可以得到这个集合的大小。