Union-find with lists
General information
Abstract Data Structure: Union-find
Implementation Invariant:
- There is an array [math]\displaystyle{ A }[/math] with index range [math]\displaystyle{ \{1,\ldots,N\} }[/math] and component type "ordered sequence of integral numbers".
- Each non-empty sequence in this array contains one of the partition sets, that is:
- Each element of [math]\displaystyle{ \{1,\ldots,N\} }[/math] is contained in exactly one sequence of [math]\displaystyle{ A }[/math].
- There are no other numbers in these sequences.
- There is an array [math]\displaystyle{ S }[/math] with index range [math]\displaystyle{ \{1,\ldots,N\} }[/math] and component type [math]\displaystyle{ N }[/math]. For [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math], [math]\displaystyle{ i }[/math] is in the sequence [math]\displaystyle{ A[S[i]] }[/math].
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:
- find: For input [math]\displaystyle{ i }[/math], just return the head of the sequence [math]\displaystyle{ A[S[i]] }[/math].
- unite: Append one sequence at the tail of the other one and clear the original position of the former sequence in [math]\displaystyle{ A }[/math]. The values [math]\displaystyle{ S[i] }[/math] of the appended elements [math]\displaystyle{ i }[/math] 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 [math]\displaystyle{ \mathcal{O}(F+N\log N) }[/math] in the worst case, where [math]\displaystyle{ F }[/math] 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 [math]\displaystyle{ \mathcal{O}(F) }[/math]. On the other hand, the contribution of the constructor to the total asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(N) }[/math]. So consider the calls to the unite method. The crucial observation is that each [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math] is moved at most [math]\displaystyle{ \mathcal{O}(\log N) }[/math] times. in total Why: Since always the shorter sequence is moved, the length of the sequence to which [math]\displaystyle{ i }[/math] belongs is at least doubled in each step in which [math]\displaystyle{ i }[/math] is moved. This proves the theorem.