Union-find with lists

http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Union-find_with_lists.html

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 in the worst case, where 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 . On the other hand, the contribution of the constructor is . So consider the calls to the unite method. The crucial observation is that each is moved at most times. Why: Since always the shorter sequence is moved, the length of the sequence to which belongs is at least doubled in each step in which is moved. This proves the theorem.