14.2 Quick Find
Keeping track of set membership...
List of Sets
Intuitively, we might first consider representing Disjoint Sets as a list of sets, e.g, List<Set<Integer>>
.
For instance, if we have N=6 elements and nothing has been connected yet, our list of sets looks like: [{0}, {1}, {2}, {3}, {4}, {5}, {6}]
. Looks good. However, consider how to complete an operation like connect(5, 6)
. We'd have to iterate through up to N
sets to find 5 and N
sets to find 6. Our runtime becomes O(N)
. And, if you were to try and implement this, the code would be quite complex.
The lesson to take away is that initial design decisions determine our code complexity and runtime.
Quick Find
Let's consider another approach using a single array of integers.
The indices of the array represent the elements of our set.
The value at an index is the set number it belongs to.
For example, we represent {0, 1, 2, 4}, {3, 5}, {6}
as:
The array indices (0...6) are the elements. The value at id[i]
is the set it belongs to. The specific set number doesn't matter as long as all elements in the same set share the same id.
connect(x, y)
connect(x, y)
Let's see how the connect operation would work. Right now, id[2] = 4
and id[3] = 5
. After calling connect(2, 3)
, all the elements with id 4 and 5 should have the same id. Let's assign them all the value 5 for now:
isConnected(x, y)
To check isConnected(x, y)
, we simply check if id[x] == id[y]
. Note this is a constant time operation!
We call this implementation "Quick Find" because finding if elements are connected takes constant time.
Code & Runtimes
N = number of elements in our DisjointSets data structure
Implementation | Constructor |
|
|
ListOfSets | Θ(N)¹ | O(N) | O(N) |
QuickFind | Θ(N) | Θ(N) | Θ(1) |
Note
1. We didn't discuss this but you can reason that having to create N distinct sets initially is Θ(N) ↩
Last updated