Major improvement to the QuickUnion algorithm.

0-quick-union-weighting.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).
The QuickUnion algorithm is explained here

##QuickUnion Weighting

Tall trees are the major reason that QuickUnion takes time to check if two items are connected.
If the height of trees can be minimized, QuickUnion will be faster.

Weighting makes sure that when two trees are connected, the smaller of the two trees is added to the larger tree (not the other way around).
In other words: the root of the smaller tree is assigned the value of the root of the larger tree.

####Example If we start with two trees:

    1       8
   / \     / \
  4   5   6   7
 / \
2   3

If we add the large tree to the small tree:

      8 
     /|\
    1 6 7
   / \
  4   5
 / \
2   3

height: 4

If we add the small tree to the large one:

    1
   /|\
  4 5 8
 /|   |\
2 3   6 7

height: 3

###The Maths A tree will only grow in size if it is added to a tree that is bigger than itself, or the same size as itself.
Otherwise, if it is connected to a tree smaller than itself, the smaller tree will be added to it and the tree will not grow in height.

Because of this, when a tree grows in height it will at least double in size.

Starting with a height of 1, the maximum amount of times that it can double in size (grow) can be found by:

2^x = N

2 - because we are doubling in size
N - there are only N number of points

x = lg(N)

lg is log base 2.

So the maximum height of any tree will be lg(N).
This means that the maximum amount of checks needed to find the root of a point is at most lg(N).

###Verdict This is good enough. The algorithm scales.

###Coding Considerations This adjustment needs another array, which keeps track of the sizes of trees.
It's important to notice that we only deal with size of trees when connecting roots (i.e. when trees are combined).

Because of this, we do not need to change the entries of the size array for every element in a tree;
We only need to change the size-array element of the root - this saves a lot of time.

QuickUnionUFWeight.java

public class QuickUnionUFWeight{
	private int[] id;
	private int[] sz;

	public QuickUnionUFWeight(int N)
	{
		id = new int[N];
		sz = new int[N];

		for (int i = 0; i < N; i++){
			id[i] = i;		
			sz[i] = 1;
		}
	}

	public boolean connected(int p, int q)
	{
		return root(p) == root(q);
	}

	public int root(int p)
	{
		while(id[p] != p){
			p = id[p];
		}
		return p;
	}

	public void union(int p, int q)
	{
		int rp = root(p);
		int rq = root(q);
		if (sz[rp] < sz[rq]){
			id[rp] = rq;
			sz[rq] += sz[rp];
		}
		else {
			id[rq] = rp;
			sz[rp] += sz[rq];
		}
	}

	public void printID()
	{
		StdOut.print("ID array ");
		for (int i = 0; i < id.length; i++)
			StdOut.print("[" + id[i] + "] ");
		StdOut.println("");
	}
}