数据结构笔记总结(10.5)基于rank的优化

基于rank的优化

上一小节对我们实现的并查集进行了基于size的优化,基于并查集中的一颗树的大小进行的优化,优化的目的在于合并两棵树的时候得到的新树整体高度尽量不要每次都进行深度的增加。

对于我们这个思想,其实更直接的一种方式通常在并查集称为基于rank的优化,这里的rank其实就是指树的高度或深度,为什么不叫做height或者depth呢?

图中展示的也是一个并查集,,0,1,2,5,6,7属于一个集合,8,3,4属于一个集合,9属于一个集合

如果我们做union(4,2)的话,4这个节点所在的根节点是8,2所在的根节点是7,那这两棵树要进行合并,合并之后,如果我们是基于size进行优化的话,4所在的这棵树的节点总数是三个,而2所在的节点总数是6个,所以根据上一小节讲的逻辑,节点总数小的那棵树去指向节点总数大的那棵树,合并之后是下面这个样子

注意,这棵树的深度变成了4,原来两棵树深度分别是2和3,经过合并之后,深度增加了,但是在我们这个例子中要注意,节点数少的这棵树,也就是以8为根节点的这棵树它的高度反而是高的,而节点数多的这棵树,也就是以7为节点的这棵树的高度反而是低的,所以更加合理的合并方案是让7这个节点指向8这个节点,深度依然是3。

这样的一种优化方案就是基于rank的优化,rank[i]表示根节点为i的树的高度

代码演示

// 我们的第四版Union-Find
public class UnionFind4 implements UF {

    private int[] rank;   // rank[i]表示以i为根的集合所表示的树的层数
    private int[] parent; // parent[i]表示第i个元素所指向的父节点
    private int size;    // 数据个数

    // 构造函数
    public UnionFind4(int size){

        rank = new int[size];
        parent = new int[size];
        this.size = size;

        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for( int i = 0 ; i < size ; i ++ ){
            parent[i] = i;
            rank[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( rank[pRoot] < rank[qRoot] )
            parent[pRoot] = qRoot;
        else if( rank[qRoot] < rank[pRoot])
            parent[qRoot] = pRoot;
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // 此时, 我维护rank的值
        }
    }
}

接下来还是在main函数中测试一下,基于千万级别的数据

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");

        UnionFind4 uf4 = new UnionFind4(size);
        time = testUF(uf4, m);
        System.out.println("UnionFind4 : " + time + " s");
    }
}

可以看出我们又对并查集做了一些优化,虽然性能差异很小。

源码下载

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

导航目录

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

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

Leave a Reply

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

立即加入 了解更多