14.2 Quick Find

Keeping track of set membership...

Professor Hug's explanation on Quick Find

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:

Set 4: {0, 1, 2, 4} | Set 5: {3, 5} | Set 6: {6}

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)

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:

Set 5: {0, 1, 2, 3, 4, 5} | Set 6: {6}

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

public class QuickFindDS implements DisjointSets {

    private int[] id;

    /* Θ(N) */
    public QuickFindDS(int N){
        id = new int[N];
        for (int i = 0; i < N; i++){
            id[i] = i;
        }
    }

    /* need to iterate through the array => Θ(N) */
    public void connect(int p, int q){
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++){
            if (id[i] == pid){
                id[i] = qid;
            }
        }
    }

    /* Θ(1) */
    public boolean isConnected(int p, int q){
        return (id[p] == id[q]);
    }
}

N = number of elements in our DisjointSets data structure

Implementation	Constructor	connect	isConnected
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) ↩