Union-find

Chapters

1. [00:00] Einführung
2. [06:27] Wie funktioniert Union-Find nochmal?
3. [07:03] Und wie war das noch mit der asymptotischen Komplexität?

General information

Representation invariant:

1. There is a nonnegative natural number $N\in \mathbb{N}$, which is constant throughout the lifetime of the object.
2. At any moment, there is a (dynamically changing) partition of $S:=\{1,\dots ,N\}$ into non-empty disjoint subsets. Each element of $S$ belongs to exactly one of these partition sets.
3. Each of these subsets $S^{\prime }\subseteq S$ is represented by an arbitrary particular member of $S^{\prime }$, which does not change as long as $S^{\prime }$ is one of the partition sets (in other words, as long as $S^{\prime }$ is not involved in any call of method unite).

Constructor: Receives $N$ as its input and initializes the union-find object such that each $i\in \{1,\dots ,N\}$ is a singleton $\{i\}$, which is represented by its unique member $i$.

Find

Input: An element $i\in \{1,\dots ,N\}$.

Output: The element $j\in \{1,\dots ,N\}$ that represents the subset to which $i$ currently belongs ($i=j$ is possible).

Precondition: none.

Postcondition: none.

Unite

Input: Two elements, $i,j\in \{1,\dots ,N\}$.

Output: none.

Precondition: The elements $i$ and $j$ do not belong to the same subset. In other words, it is find$(i)\ne$ find$(j)$.

Postcondition: The subsets to which $i$ and $j$ belong are united (the representative of the united set is not specified).

Known implementations

1. Union-find with lists