Union-find with lists

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

Abstract Data Structure: Union-find

Implementation Invariant:

1. There is an array $A$ with index range $\{1,\dots ,N\}$ and component type "ordered sequence of integral numbers".
2. Each non-empty sequence in this array contains one of the partition sets, that is:
   1. Each element of $\{1,\dots ,N\}$ is contained in exactly one sequence of $A$.
   2. There are no other numbers in these sequences.
3. There is an array $S$ with index range $\{1,\dots ,N\}$ and component type $N$. For $i\in \{1,\dots ,N\}$, $i$ is in the sequence $A[S[i]]$.

For a non-empty sequence in , the head of this sequence is the representative of the corresponding partition set.

Methods

The find and unite methods are quite simple and need no separate wiki pages:

1. find: For input $i$, just return the head of the sequence $A[S[i]]$.
2. unite: Append one sequence at the tail of the other one and clear the original position of the former sequence in $A$. The values $S[i]$ of the appended elements $i$ have to be updated according to item 3 of the implementation invariant.

Asymptotic complexity

Statement: If always the shorter sequence is appended to the longer sequence (ties arbitrarily broken), the asymptotic complexity is $\mathcal{O}(F+N\log N)$ in the worst case, where $F$ is the number of calls to the find method.

Proof: Obviously, a single call to the find method requires constant time. So, the contribution of all find operations is in $\mathcal{O}(F)$. On the other hand, the contribution of the constructor to the total asymptotic complexity is in $\mathcal{O}(N)$. So consider the calls to the unite method. The crucial observation is that each $i\in \{1,\dots ,N\}$ is moved at most $\mathcal{O}(\log N)$ times in total because: Since always the shorter sequence is moved, the length of the sequence to which $i$ belongs is at least doubled in each step in which $i$ is moved. This proves the theorem.