Union-find: Difference between revisions
(→unite) |
|||
| Line 2: | Line 2: | ||
'''Representation invariant:''' | '''Representation invariant:''' | ||
# There is a natural number <math>N\in\mathbb{N}</math>, which is constant throughout the lifetime of the object. | # There is a nonnegative natural number <math>N\in\mathbb{N}</math>, which is constant throughout the lifetime of the object. | ||
# At any moment, there is a (dynamically changing) partition of <math>S:=\{1,\ldots,N\}</math> into non-empty disjoint subsets. Each element of <math>S</math> belongs to exactly one of these partition sets. | # At any moment, there is a (dynamically changing) partition of <math>S:=\{1,\ldots,N\}</math> into non-empty disjoint subsets. Each element of <math>S</math> belongs to exactly one of these partition sets. | ||
# Each of these subsets <math>S'\subseteq S</math> is represented by an arbitrary particular member of <math>S'</math>, which does not change as long as <math>S'</math> is one of the partition sets. | # Each of these subsets <math>S'\subseteq S</math> is represented by an arbitrary particular member of <math>S'</math>, which does not change as long as <math>S'</math> is one of the partition sets. | ||
Revision as of 12:39, 20 June 2015
General information
Representation invariant:
- There is a nonnegative natural number [math]\displaystyle{ N\in\mathbb{N} }[/math], which is constant throughout the lifetime of the object.
- At any moment, there is a (dynamically changing) partition of [math]\displaystyle{ S:=\{1,\ldots,N\} }[/math] into non-empty disjoint subsets. Each element of [math]\displaystyle{ S }[/math] belongs to exactly one of these partition sets.
- Each of these subsets [math]\displaystyle{ S'\subseteq S }[/math] is represented by an arbitrary particular member of [math]\displaystyle{ S' }[/math], which does not change as long as [math]\displaystyle{ S' }[/math] is one of the partition sets.
Constructor: Receives [math]\displaystyle{ N }[/math] as its input and initializes the union-find object such that each [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math] is a singleton [math]\displaystyle{ \{i\} }[/math], which is represented by its unique member [math]\displaystyle{ i }[/math].
find
Input: An element [math]\displaystyle{ i\in\{1,\ldots,N\} }[/math].
Output: The element [math]\displaystyle{ j\in\{1,\ldots,N\} }[/math] that represents the subset to which [math]\displaystyle{ i }[/math] currently belongs ([math]\displaystyle{ i=j }[/math] is possible).
Precondition: none.
Postcondition: none.
unite
Input: Two elements, [math]\displaystyle{ i,j\in\{1,\ldots,N\} }[/math].
Output: none.
Precondition: The elements [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] do not belong to the same subset. In other words, it is find[math]\displaystyle{ (i)\neq }[/math] find[math]\displaystyle{ (j) }[/math].
Postcondition: The subsets to which [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] belong are united (the representative of the united set is not specified).