Weighted Quick-Union with Path Compression algorithm-Union Find

Question

I have a project in which i have to implement a weighted quick-union with path compression algorithm.After seeing a number of others source code,i ended up in this:

public class UnionFind {

private int[] parent;
private int[] size;
private int maxItemCount;      // maximum number of items from {0,1,...,N-1}
private int numItems;      // number of items created

UnionFind(int N) {
    this.N = N;
    this.K = 0;
    parent = new int[N];
    size = new int[N];
    for (int i = 0; i < N; i++) {
        parent[i] = -1;
        size[i] = 0;
    }
}

void makeSet(int v) {
    if (parent[v] != -1) return; // item v already belongs in a set
    parent[v] = v;
    size[v] = 1;
    K++;
}

int find(int v) {
    if (v == parent[v]) {
        return v;
    }
       return parent[v] = find(parent[v]);
    }


void unite(int v, int u) {
    int x=find(v);
    int y=find(u);
    if(x!=y) {
        parent[x]=y;
    }
}

int setCount() {
    int item=0;
    for(int i=0;i<parent.length;i++) {
        if(i==parent[i]) {
            item++;
        }
    }
    return item; // change appropriately 
}

int itemCount() {
    return K;
}

The task which has been assigned to me is to complete properly the following methods :

1. int find(int v)
2. void unite(int v,int u)
3. setCount(int v)

Well,the algorithm seems to be slow and i can't find a suitable solution.

---

Answer 1

Here are some issues:

• The size information is not used, yet that information is crucial in keeping the desired performance. Most importantly, in unite:

  • size should be kept updated: the united set will have as many members as the two given sets had
  • size should determine which of the two root nodes should be the root of the united set, as this will keep the trees balanced

• setCount has O(n) time complexity. It could give the information in O(1) time if you would keep track of that number in a member variable. I'd call it numSets. If setCount() is called a lot, this change will have a positive effect.

Not a problem, but naming variables as N and K is not helping to make the code readable. Why not give names that actually tell what they are, so you don't need to accompany their definitions with a comment to give that explanation?

Here is your code with those adaptations:

public class UnionFind {
    
    private int[] parent;
    private int[] size;
    private int maxItemCount;
    private int numItems;
    private int numSets;
    
    UnionFind(int maxItemCount) {
        this.maxItemCount = maxItemCount;
        numItems = 0;
        numSets = 0;
        parent = new int[maxItemCount];
        size = new int[maxItemCount];
        for (int i = 0; i < maxItemCount; i++) {
            parent[i] = -1;
            size[i] = 0;
        }
    }
    
    void makeSet(int v) {
        if (parent[v] != -1) return; // item v already belongs in a set
        parent[v] = v;
        size[v] = 1;
        numItems++;
        numSets++;  // Keep track of number of sets
    }
    
    int find(int v) {
        if (v == parent[v]) {
            return v;
        }
        return parent[v] = find(parent[v]);
    }
    
    void unite(int v, int u) {
        int x = find(v);
        int y = find(u);
        if (x != y) {
            numSets--; // A union decreases the set count
            // Determine which node becomes the root
            if (size[x] < size[y]) {
                parent[x] = y;
                size[y] += size[x]; // Adapt size
            } else {
                parent[y] = x;
                size[x] += size[y]; // Adapt size
            }
        }
    }
    
    int setCount() {
        return numSets; // Kept track of it
    }
    
    int itemCount() {
        return numItems;
    }
}