并查集

并查集

并查集，又叫不相交集合。可以用数组实现的树状结构

查找：查找元素所在的集合

合并：将两个元素所在的集合合并为一个集合

Quick Find 实现，同一个集合的所有元素指向一个节点。查找时间复杂度O(1)，合并时间复杂度O(n)

Quick Union实现，树的形式保存，查找的时候需要查到根结点，查找时间复杂度O(logn)，合并的时间复杂度O(logn)

接口定义

    /**
     * 查找v所属的集合（根节点）
     * @param v
     * @return
     */
    public abstract int find(int v);

    /**
     * 合并v1、v2所在的集合
     */
    public abstract void union(int v1, int v2);

    /**
     * 检查v1、v2是否属于同一个集合
     */
    public boolean isSame(int v1, int v2) {
        return find(v1) == find(v2);
    }

优化

在quick union中，讲一个树接到另一个树的时候，可能会出现极度不平衡，甚至退化成链表

优化方案：

1. 基于size，元素少的树，嫁接到元素多的树
2. 基于rank 树高度，矮的树嫁接到高的树

基于size也会出现不平衡，整体效果比基于rank差

基于rank的优化，可以对树进行继续优化：

1. 路径压缩：在find的时候将所有结点都指向根结点，从而降低树高度
2. 路径分裂：使路径上的每个结点都指向其祖父结点
3. 路径减半：使路径上的每隔一个结点都指向其祖父结点

自定义类型

并查集是基于整型数据，其他类型使用并查集方案

1、通过一些方法将自定义类型转为整型后使用

2、使用链表+映射