Union-find with lists: Difference between revisions
No edit summary |
|||
| Line 16: | Line 16: | ||
The find and unite methods are quite simple and need no separate wiki pages: | The find and unite methods are quite simple and need no separate wiki pages: | ||
# find: For input , just return the [[Sets and sequences#Ordered and sorted sequences|head]] of the sequence <math>A[S[i]]</math>. | # find: For input <math>i</math>, just return the [[Sets and sequences#Ordered and sorted sequences|head]] of the sequence <math>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>A</math>. The values <math>S[i]</math> of the appended elements <math>i</math> have to be updated according to item 3 of the implementation invariant. | # unite: Append one sequence at the tail of the other one and clear the original position of the former sequence in <math>A</math>. The values <math>S[i]</math> of the appended elements <math>i</math> have to be updated according to item 3 of the implementation invariant. | ||
Revision as of 13:38, 20 June 2015
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 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.