最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(10.4)基于size的优化

    并查集的优化

    前两节我们实现了两种并查集,第一版的并查集其实就是使用数组来模拟每个数据所属的集合是谁,第二版虽然依然使用数组来进行数据关系的存储,但整体思路上和第一版的并查集是截然不同的,让数据形成了一种比较奇怪的树结构,或者说是森林结构。

    改进并查集

    这里我们先回忆一下第二版的Quick Union的过程,首先执行union(0,1),结果如下

    下面执行union(0,2)

    再执行union(0,3)

    相信大家已经发现问题了,现在union过程中由于没有对合并的那两个元素所在的树的形状做判断,很多时候合并的这个过程会不断的增加树的高度,甚至在一些极端的情况下得到的树是一个链表的样子,具体如何解决这样的问题呢?

    解决方案:考虑size

    假设当前的并查集是这个样子,如果想union(4,9)的话,4所在的根节点是8,直接就让8指向9的话最终得到的树是这个样子,深度达到了4

    但是在这种情况下,其实我们完全可以让9去指向4所在的这棵树的根节点,直接让9去指向8,这种情况下,它的高度只有3,换句话说,让节点个数小的那棵树它的根节点去指向节点个数多的那棵树的根节点,这样做,高概率的形成的这棵树的深度会比较低,这个优化的思路其实是非常简单的。

    具体实现第三个版本

    // 我们的第三版Union-Find
    public class UnionFind3 implements UF{
    
        private int[] parent; // parent[i]表示第一个元素所指向的父节点
        private int[] sz;     // sz[i]表示以i为根的集合中元素个数
        private int size;    // 数据个数
    
        // 构造函数
        public UnionFind3(int size){
    
            parent = new int[size];
            sz = new int[size];
            this.size = size;
            // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
            for(int i = 0 ; i < size ; i ++){
                parent[i] = i;
                sz[i] = 1;
            }
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        // 查找过程, 查找元素p所对应的集合编号
        // O(h)复杂度, h为树的高度
        private int find(int p){
            if(p < 0 && p >= size)
                throw new IllegalArgumentException("p is out of bound.");
    
            // 不断去查询自己的父亲节点, 直到到达根节点
            // 根节点的特点: parent[p] == p
            while( p != parent[p] )
                p = parent[p];
            return p;
        }
    
        // 查看元素p和元素q是否所属一个集合
        // O(h)复杂度, h为树的高度
        @Override
        public boolean isConnected( int p , int q ){
            return find(p) == find(q);
        }
    
        // 合并元素p和元素q所属的集合
        // O(h)复杂度, h为树的高度
        @Override
        public void unionElements(int p, int q){
    
            int pRoot = find(p);
            int qRoot = find(q);
    
            if(pRoot == qRoot)
                return;
    
            // 根据两个元素所在树的元素个数不同判断合并方向
            // 将元素个数少的集合合并到元素个数多的集合上
            if(sz[pRoot] < sz[qRoot]){
                parent[pRoot] = qRoot;
                sz[qRoot] += sz[pRoot];
            }
            else{
                parent[qRoot] = pRoot;
                sz[pRoot] += sz[qRoot];
            }
        }
    }
    

    测试一下这三个版本

    import java.util.Random;
    public class Main {
        private static double testUF(UF uf, int m){
    
            int size = uf.getSize();
    
            Random random = new Random();
            long startTime = System.nanoTime();
    
            for(int i = 0 ; i < m ; i ++){
                int a = random.nextInt(size);
                int b = random.nextInt(size);
                uf.unionElements(a, b);
            }
            for(int i = 0 ; i < m ; i ++){
                int a = random.nextInt(size);
                int b = random.nextInt(size);
                uf.isConnected(a, b);
            }
            long endTime = System.nanoTime();
    
            double time = (endTime - startTime) / 1000000000.0;
            return time;
        }
    
        public static void main(String[] args) {
    
            int size = 100000;
            int m = 100000;
            double time;
    
            UnionFind1 uf1 = new UnionFind1(size);
            time = testUF(uf1, m);
            System.out.println("UnionFind1 : " + time + " s");
    
            UnionFind2 uf2 = new UnionFind2(size);
            time = testUF(uf2, m);
            System.out.println("UnionFind2 : " + time + " s");
    
            UnionFind3 uf3 = new UnionFind3(size);
            time = testUF(uf3, m);
            System.out.println("UnionFind3 : " + time + " s");
        }
    }
    

    运行程序,输出结果

    看我们第三个版本,时间效率有了飞跃的提升

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(10.4)基于size的优化

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 192会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 614稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级