Tutorial by Examples

Union find data structures provide the following operations: make_sets(n) initializes a union-find data structure with n singletons find(i) returns a representative for the set of element i union(i,j) merges the sets containing i and j We represent our partition of the elements 0 to n - 1 by...

The most basic implementation of a union-find data structure consists of an array parent storing the a parent element for every element of the structure. Following these parent 'pointers' for an element i leads us to the representative j = find(i) of the set containing i, where parent[j] = j holds....

If we do many merge operations on a union-find data structure, the paths represented by the parent pointers might be quite long. Path compression, as already described in the theory part, is a simple way of mitigating this issue. We might try to do path compression on the whole data structure after...

In our current implementation of merge, we always choose the left set to be the child of the right set, without taking the size of the sets into consideration. Without this restriction, the paths (without path compression) from an element to its representative might be quite long, thus leading to la...

Another heuristic commonly used instead of union by size is the union by rank heuristic Its basic idea is that we don't actually need to store the exact size of the sets, an approximation of the size (in this case: roughly the logarithm of the set's size) suffices to achieve the same speed as union...

While in combination with path compression, union by rank nearly achieves constant time operations on union-find data structures, there is a final trick that allows us to get rid of the rank storage altogether by storing the rank in out-of-bounds entries of the parentarray. It is based on the follow...