Disjoint Sets¶
| Signature | Description |
|---|---|
void makeSet(T item) | Creates a new set containing just the given item and with a new integer id. |
int findSet(T item) | Returns the integer id of the set containing the given item. |
boolean union(T item1, T item2) | If the given items are in different sets, merges those sets and returns true. Otherwise does nothing and returns false. |
The disjointsets package contains the disjoint sets data structures required by Kruskal’s algorithm. We include a default, inefficient implementation in the skeleton.
The inefficient implementation will be replaced by the optimized UnionBySizeCompressingDisjointSets implementation to generate mazes.
An Optimized Implementation¶
Task
Implement UnionBySizeCompressingDisjointSets using union-by-size, path compression, and array representation optimizations.
Implementation notes:
- We recommend reviewing the lecture slides and section materials before implementing your disjoint sets.
- The Gradescope tests will directly inspect the
pointersfield so be sure to store the array representation of your disjoint sets there.
In the next section, you will use your optimized disjoint sets implementation to speed up KruskalMinimumSpanningTreeFinder.