Note: This post is part of the Data Structures and Algorithm series. To see more posts from this series, click here. The illustrations below are inspired by the Algorithms, Part I course on Coursera. All code examples from this series can be found here.
A disjointset (also referred to as a unionfind data structure) is a data structure that tracks a set of elements partitioned into a group of disjoint subsets (also known as connected components). Given this type of data structure, there are multiple algorithms that can be used to solve the two major equations for a disjointset, the Union command and the Find query, which we'll go into more detail below.
Dynamic Connectivity
 A dynamic connectivity structure maintains information about the connected components of a graph.

Given a set of N objects:
 Connect two objects (the Union command)
 Determine if there is a path connecting the two objects (the Find query)
UnionFind Illustration
Quick Find
 Quick Find is an Eager algorithm also used to solve the dynamic connectivity problem.

The Find query for this algorithm is very efficient and is measured in constant time.
 Given id[] of size N, check if p and q are connected.

The Union command is measured in quadratic time because the time to resolve is dependent on the size of the array and the number of values that must change as a result.
 When changing a value of
id[q]
, you must also change all entries whose value is equal (connected) toid[q]
as well.
 When changing a value of
Quick Find Illustration
Quick Find Implementation
import DisjointSet from "./DisjointSet"
class QuickFind implements DisjointSet {
disjointSet: number[]
constructor(quantity: number) {
this.disjointSet = []
for (let i = 0; i < quantity; i++) this.disjointSet[i] = i
}
connected = (p: number, q: number): boolean => {
return this.disjointSet[p] === q
}
union = (p: number, q: number): void => {
const pid = this.disjointSet[p]
const qid = this.disjointSet[q]
this.disjointSet.forEach((value, index) => {
if (value === pid) {
this.disjointSet[index] = qid
}
})
}
}
export default QuickFind
Quick Union
 Quick Union is a Lazy algorithm that, again, is used to solve the dynamic connectivity problem.
 Data structures implementing this algorithm are represented as trees in order to find the connected root of each element.

The Find query requires a traversal up the tree:
 Given id[] of size N, check if p and q have the same root.

The Union command requires the find query in order to determine each element's root before merging.
 This command is measured in linear time because in order to merge the connected components containing p and q, we must set the id of p's root to the id of q's root.
Quick Union Illustration
Quick Union Implementation
import DisjointSet from "./DisjointSet"
class QuickUnion implements DisjointSet {
disjointSet: number[]
constructor(quantity: number) {
this.disjointSet = []
for (let i = 0; i < quantity; i++) this.disjointSet[i] = i
}
private root(valueToCheck: number): number {
while (this.disjointSet[valueToCheck] !== valueToCheck) {
valueToCheck = this.disjointSet[valueToCheck]
}
return valueToCheck
}
private isDirectChild(p: number, q: number): boolean {
return this.disjointSet[p] === q
}
connected(p: number, q: number): boolean {
if (this.isDirectChild(p, q)) return true
return this.root(p) === this.root(q)
}
union(p: number, q: number): void {
const rootP = this.root(p)
const rootQ = this.root(q)
this.disjointSet[rootP] = rootQ
}
}
export default QuickUnion
Improvements to Quick Union
Weighted Quick Union

We can improve Quick Union by "weighting" our algorithm. What this means is that anytime a Union operation is performed, we will always link the root of the smaller tree to the root of the larger tree.
 This helps to keep the overall tree structure relatively flat, compared to a normal quickunion tree (as pictured below), and ensures each node is never too far from the overall root node.
 The Find query takes the time proportional to the depth of p and q.
 Because we are always setting the root of the smaller tree to that of the larger tree, the depth of any node is at most log N (where N is the number of nodes in the overall tree).
Weighted Quick Union Illustration
Weighted Quick Union Implementation
For the weighted quick union implementation, you can see below that our Find query remains the same. For the Union operation, however, we are incrementing the size of the larger root by the size of the smaller root.
import DisjointSet from "./DisjointSet"
class WeightedQuickUnion implements DisjointSet {
disjointSet: number[]
size: number[]
constructor(quantity: number) {
this.disjointSet = []
this.size = []
for (let i = 0; i < quantity; i++) {
this.disjointSet[i] = i
this.size[i] = 1
}
}
private root(valueToCheck: number): number {
while (this.disjointSet[valueToCheck] !== valueToCheck) {
valueToCheck = this.disjointSet[valueToCheck]
}
return valueToCheck
}
private isDirectChild(p: number, q: number): boolean {
return this.disjointSet[p] === this.disjointSet[q]
}
connected(p: number, q: number): boolean {
if (this.isDirectChild(p, q)) return true
return this.root(p) === this.root(q)
}
union(p: number, q: number): void {
const rootP = this.root(p)
const rootQ = this.root(q)
if (rootP === rootQ) return
if (this.size[rootP] <= this.size[rootQ]) {
this.disjointSet[rootP] = rootQ
this.size[rootQ] += this.size[rootP]
} else {
this.disjointSet[rootQ] = rootP
this.size[rootP] += this.size[rootQ]
}
}
}
export default WeightedQuickUnion
Weighted Quick Union with Path Compression

This algorithm can be improved even further by compressing the path to the overall root.
 So, after computing the root of p, for any node that was passed over (6, 3, 1 in the following illustration), we'll set it to point to the new root as well.
 This causes our overall tree to flatten even further, decreasing the time complexity to almost linear.
Weighted Quick Union with Path Compression Illustration
Weighted QU with Path Compression Implementation
For this implementation, we're going to update our root
method so that for each traversal to an object's root, we'll set the value of every other node in the path to point to its grandparent, thereby halving the length to the object's root.
private root(valueToCheck: number): number {
while (this.disjointSet[valueToCheck] !== valueToCheck) {
this.disjointSet[valueToCheck] = this.disjointSet[
this.disjointSet[valueToCheck]
];
valueToCheck = this.disjointSet[valueToCheck];
}
return valueToCheck;
}