Introduction
In this lab, you’ll create UnionFind
which will be used to solve the dynamic connectivity problem. As mentioned in discussion “Union Find” is a synonym for “Disjoint Sets”.
Your implementation of the Union Find data structure will be the most advanced version from lecture, namely Weighted Quick Union. For more information about this please reference the slides from lecture. To better visualize and help you understand the operations on disjoint sets check out this online datastructure visualizer. Be sure to turn on Union by Rank where Rank = # of nodes (Union by Rank is just another way of saying “Weighted Quick Union”).
Optionally, you may also implement path compression. If you do so, make sure to enable Path Compression in the visualizer linked above.
Weighted Quick Union
A skeleton will be provided in which you will have to fill in the following methods to complete the data structure:
public UnionFind(int n):
Creates a UnionFind data structure holdingn
vertices. Initially, all vertices are in disjoint sets.public void validate(int v1)
: Throws an exception ifv1
is not a valid index.public int sizeOf(int v1)
: Returns the size of the setv1
belongs to.public int parent(int v1)
: Returns the parent ofv1
. Ifv1
is the root of a tree, returns the negative size of the tree for whichv1
is the root.public boolean connected(int v1, int v2)
: Returns true if nodesv1
andv2
are connected.public void union(int v1, int v2)
: Connects two elementsv1
andv2
together.v1
andv2
can be any valid elements, and a unionbysize heuristic is used. If the sizes of the sets are equal, tie break by connectingv1
’s root tov2
’s root. Unioning a vertex with itself or vertices that are already connected should not change the sets, but it may alter the internal structure of the data structure.public int find(int v1)
: Returns the root of the setv1
belongs to. Pathcompression is employed allowing for fast searchtime.
For the above functions you should also correctly handle faulty inputs, e.g if invalid vertices are passed into the above functions, throw an IllegalArgumentException.
When implementing UnionFind
feel free to either follow the above order or any other order which makes sense to you. Please note that that these methods are not independent from one another, and some methods might be useful as helper methods for others.
Optional Questions / Exercises
Below are a number of exercises that deal with Quick Find, Weighted Quick Union, and some variants of them. These questions are not required, but will serve as good practice in thinking about the differences between these differing implementations. The answers are displayed in white text, so if you want to check what you think highlight the line to reveal the text.
Quick Find

Using the Quick Find algorithm with items, what is the worstcase runtime for the find operation?
Answer: The worst case runtime is

Using the Quick Find algorithm with items, what is the worstcase runtime for the union operation?
Answer: The worst case runtime is .
Weighted Quick Union
Define a fully connected DisjointSets
object as one in which connected returns true for any arguments, due to prior calls to union
. Suppose we have a fully connected DisjointSets
object with 6 items. Give the best and worst case height for the two implementations below. We define height as the number of links from the root to the deepest leaf, so a tree with 1 element has a height of 0. Give your answer as an exact value. Assume HeightedQuickUnion
is like WeightedQuickUnion
, except uses height instead of size/weight to determine which subtree is the new root. Hint: Try drawing out a few disjoint set trees and think about the different possible sequences of union operations that will result in the maximum height vs. the minimum height tree.

What is the bestcase height for a
WeightedQuickUnion
containing 6 items?Answer: The best case height is 1.

What is the worstcase height for a
WeightedQuickUnion
containing 6 items?Answer: The worst case height is 2.

What is the bestcase height for a
HeightedQuickUnion
containing 6 items?Answer: The best case height is 1.

What is the worstcase height for a
HeightedQuickUnion
containing 6 items?Answer: The worse case height is 2.
TA Overview
At the end of lab, your TA will go over the reference solution to UnionFind
. This will be helpful if you haven’t finished the lab, since we don’t want you to be stuck working on lab too much outside of lab. (This is also an incentive for you to go to lab!)
Submission and Recap
In this lab we covered the implementation of Weighted Quick Union, optionally with path compression. You already know the drill, but just to remind you make sure to push your code to GitHub and submit to Gradescope to get credit for this lab. We will only be grading the code you have written in UnionFind
.