In my previous article I wrote about the basic idea of Union Find data structure, that is called Quick Find. Please click here for the article if you haven’t seen it yet. At the end of the article we figured that it was not that efficient. In this article I will talk about Quick Union algorithm that will solve the issue that was making Quick Find algorithm inefficient.
Problem
As Quick Find algorithm, this algorithm also finds out if any two elements are connected. If not connected, then connects them. This problem is called dynamic connectivity problem. The goal of this problem is to improve Quick Find algorithm so it becomes more efficient. The primarily focus will be on the ‘union’ method. That was the most inefficient method. Here a lazy approach for the union method will help. In the Quick Find algorithm, every time we did a union, we had to iterate through the whole array. That’s not happening here. We will only change one id.
Example of Quick Union
Here I will show some examples, the way union of two ids works in Quick Union algorithm. The first row will show the position of each element and second row represents the ids.
What is happening in all those examples above? In Union (3, 4), we simply change id of 3 to id of 4. In Union (3, 8) also we only change id of 3 to id of 8. If it would be a Quick Find algorithm, we would change all the ids that are same as id of 3 to id of 8. Here we are changing only one that is mentioned in this union. That’s why it’s called the lazy approach. All the four unions can be shown in the picture as follows:
In this picture, root of 3 is 4, root of 4 is 9. So, overall root is 9. In this algorithm, a different method will be constructed to find this overall root.
Solution
In this picture, root of 3 is 4, root of 4 is 9. So, overall root is 9. In this algorithm, a different method will be constructed to find this overall root.
These are the steps to follow to solve this problem.
Step 1:
Step 1 will be exactly the same as Quick Find algorithm. That is to develop a constructor with an input N. N is the size of the data. An array of range N will be generated. Each element is an id that is the same as the element position starting from 0. Such as id of position 1 is 1, id of position 0 is 0, id of position 7 is 7 in the array to start with.
Step 2:
In this step, we need to find root the way it is described after the picture above. Root of i is id[id[…id[i]…]].
Step 3:
Define the connect method that will return if root of both the elements are already same. If this returns ‘true’ then program is over. If this returns ‘false’, step 4 will be implemented.
Step 4:
Finally, define the class union. ‘union’ method takes two integer inputs. For example, if the two inputs are p and q, id of p will change to id of q.
Here I am showing both Java and Python implementation.
Java Implementation:
public class QuickUnion {
private int[] id;
public QuickUnion(int N) {
id = new int[N];
for (int i=0; i<N; i++) {
id[i] = i;
}
}
public int find(int i) {
while(id[i] != i) {
i=id[i];
}
return i;
}
private boolean connect(int p, int q) {
return find(p) == find(q);
}
public int[] union(int p, int q) {
int pid = find(p);
int qid = find(q);
id[pid]= qid;
return id;
}
public static void main(String[] args) {
QuickUnion qu = new QuickUnion(10);
System.out.println(Arrays.toString(qu.union(2,7)));
}
}
Python Implementation:
class QuickUnion(object):
def __init__(self, N):
self.lst = list(range(N))
def find(self, ind):
while ind != self.lst[ind]:
ind = self.lst[ind]
return ind
def connect(self, p, q):
return self.find(p) == self.find(q)
def union(self, p, q):
pid = self.find(p)
self.lst[pid] = self.find(q)
first = QuickUnion(10)
print(first.union(2,7))
print(first.lst)
Cost of the Model
In this algorithm union method is far more efficient than the union method of Quick Find. As you can see there is no for loop. So, it doesn’t have to iterate through the whole id array. But sometimes find operation can be very expensive. Look at the picture of the tree above. If all the ids keep connecting in one tree such that the tree becomes a skinny tall tree, finding one element from that tree could be very expensive. In the next article, we will improve that part.
