2017-11-14

## Idea

Basically, the class contains two arrays, parents and ranks.

1. parents stores the parent ID of a given ID.
2. ranks stores the rank of roots.

It supports two operations, find and union

1. For find(n1), it will trace back from given ID to its parent, and parent’s parent, until reaching an element without a parent, i.e. a root.
• an optimization here is attaching every elements on this tracing path to the final root, so that the height of the tree is reduced dramatically
2. For union(n1, n2), first we find the roots of two elements. If two roots are the same, do nothing (but it can be a useful tool to check whether an edge between two nodes makes cycle in a graph). Else, based on the ranks of two roots, we attach one to another to make the tree as balanced as possible.

## Analysis

### Union

Union operation takes $O(1)$ time.

### Find

If we don’t do path shortening, the height of the tree is no more than $O(\log n)$, $n$ is the number of elements in the tree. Because the tree is balanced and a non-leaf node can have no less than 2 children. The time for a find operation is $O(\log n)$.

If we do the path shortening, there is a tricky proof says the time complexity for a sequence of $m$ operations is $O((m+n)\sqrt{\log n})$. There is a even more tricky one to lower this upper bound. I may post the proof later.

## Implementation

package unionFind;

import java.util.Arrays;
import java.util.Queue;

public class UnionFind {
private int[] parents;
private int[] ranks;

public UnionFind(int size) {
parents = new int[size];
Arrays.fill(parents, -1);
ranks = new int[size];
}

public int find(int curId) {
while (parents[curId] != -1) {
queue.offer(curId);
curId = parents[curId];
}
while (!queue.isEmpty()) {
parents[queue.poll()] = curId;
}
return curId;
}

public void union(int root1, int root2) {
root1 = find(root1);
root2 = find(root2);
if (root1 == root2) {
return;
}
if (ranks[root1] < ranks[root2]) {
parents[root1] = root2;
} else if (ranks[root2] < ranks[root1]) {
parents[root2] = root1;
} else {
ranks[root1]++;
parents[root2] = root1;
}
}
}