Class WeightedQuickUnionDisjointSet

A QuickUnionDisjointSet refinement which improves the performance of Find by minimizing the height of trees in the forest when merging them in Union(Int32, Int32).

Inheritance
System.Object
QuickUnionDisjointSet
WeightedQuickUnionDisjointSet
PathCompressionWeightedQuickUnionDisjointSet
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.DisjointSets
Assembly: MoreStructures.dll
Syntax
public class WeightedQuickUnionDisjointSet : QuickUnionDisjointSet, IDisjointSet
Remarks

By merging by rank, the increment of rank of the trees in the forest when merging is minimized, and the forest is kept as flat as possible after the Union(Int32, Int32) operation.
Keeping trees flat is the way to ensure sub-linear, Time Complexity in AreConnected(Int32, Int32) and Find(Int32), which in the specific case become logarithmic in time.

Constructors

| Improve this Doc View Source

WeightedQuickUnionDisjointSet(Int32)


Initializes the ranks of all singleton trees to 0.

Declaration
public WeightedQuickUnionDisjointSet(int valuesCount)
Parameters
Type Name Description
System.Int32 valuesCount

Properties

| Improve this Doc View Source

Ranks

Maps the i-th item of the Disjoint Set to its rank in the tree structure, they belong to.
I-th items which are leaves have rank equal to 0.

Declaration
protected int[] Ranks { get; }
Property Value
Type Description
System.Int32[]
Remarks

The rank of a node in the tree is an upper bound for its height.
Ranks are used, instead of heights, because keeping ranks correct is easier than keeping heights correct.

Methods

| Improve this Doc View Source

GetRanks()

Returns a copy of the ranks of the trees of the forest representing the Disjoint Set.

Declaration
public IList<int> GetRanks()
Returns
Type Description
IList<System.Int32>
| Improve this Doc View Source

Union(Int32, Int32)

Declaration
public override void Union(int first, int second)
Parameters
Type Name Description
System.Int32 first
System.Int32 second
Overrides
Remarks

ALGORITHM
- It first finds the root R1 of first and the root R2 of second, by running Find(Int32) on each item.
- Then, it checks the rank of R1, H1 and R2, H2 and uses them to decide whether to attach R1 to R2 or viceversa.
- If H1 >= H2, it attaches R2 as immediate child of R1, by setting the parent of R2 to R1.
- Otherwise, it attaches R1 as immediate child of R2, by setting the parent of R1 to R2.
- This way the two three now are merged into a single one, which means that all items of the two trees, including first and second are now in the same set.
- Moreover, by merging based on ranks H1 and H2, the rank of the resulting tree is minimized.
- Finally the rank of the new root (R1 or R2), is updated, to reflect the merge.

COMPLEXITY
- Find the two roots takes a time proportional to the rank of the two trees.
- Thanks to the "merging by rank", unlike in QuickUnionDisjointSet, the rank of each tree in the forest is not O(n) in the worst case, but O(log(n)).
- Attaching one root as child of the other is a constant-time operation, since it only requires setting the parent in the list of parents, which is O(1) work.
- Updating the rank of the root of the merged tree is also a constant-time operation.
- Therefore, Time Complexity is O(log(n)). Space Complexity is O(1).

Implements

Extension Methods