Java – weighted fast joint path compression algorithm

There is a "weighted fast joint path compression" algorithm

code:

public class WeightedQU 
{
    private int[] id;
    private int[] iz;

    public WeightedQU(int N)
    {
        id = new int[N];
        iz = new int[N];
        for(int i = 0; i < id.length; i++)
        {
            iz[i] = i;
            id[i] = i;
        }
    }

    public int root(int i)
    {
        while(i != id[i])
        {
            id[i] = id[id[i]];   // this line represents "path compression"
            i = id[i];
        }
        return i;
    }

    public boolean connected(int p,int q)
    {
        return root(p) == root(q);
    }

    public void union(int p,int q)   // here iz[] is used to "weighting"
    {
        int i = root(p);
        int j = root(q);
        if(iz[i] < iz[j])
        {
            id[i] = j;
            iz[j] += iz[i];
        }
        else
        {
            id[j] = i;
            iz[i] += iz[j];
        }
    }
}

Question:

>How does path compression work? ID [i] = ID [ID [i]] means that we only reach the second connection of our node, not the root. > Iz [] contains an integer from 0 to N - 1 Iz [] how can we know the number of elements in a collection?

Can someone explain it for me

Solution

First understand that ID is a forest ID [i] is my parents If Id [i] = = I mean I am a root

For some roots I (where id [i] = = I), iz [i] is based on the number of elements in my tree

public int root(int i)
{
    while(i != id[i])
    {
        id[i] = id[id[i]];   // this line represents "path compression"
        i = id[i];
    }
    return i;
}

When we climb the tree and find the root, we move the node from their parents to their grandparents This partially flattens the tree Please note that this operation does not change the tree to which the node belongs. This is the owner we are interested in. This is path compression technology

(do you really notice that the loop is correct? While (I = = ID [i]) terminates once I am a root node)

There is a transcription error in the code:

for(int i = 0; i < id.length; i++)
{
    iz[i] = i; // WRONG
    id[i] = i;
}

This is the correct version:

for(int i = 0; i < id.length; i++)
{
    iz[i] = 1; // RIGHT
    id[i] = i;
}

Iz [i] is the number of elements of the tree according to my tree (or if I am not the root, then iz [i] is undefined) So it should be initialized to 1, not me Initially, each element is a separate single tree of size 1