Union-find with lists

General information

Abstract Data Structure: Union-find

Implementation Invariant:

1. 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".
2. Each non-empty sequence in this array contains one of the partition sets, that is:
   1. Each element of [math]\displaystyle{ \{1,\ldots,N\} }[/math] is contained in exactly one sequence of [math]\displaystyle{ A }[/math].
   2. There are no other numbers in these sequences.
3. 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:

1. find: For input [math]\displaystyle{ i }[/math], just return the head of the sequence [math]\displaystyle{ A[S[i]] }[/math].
2. 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 because: 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.