CSC300 / CSC402: Comparing UF implementations [9/9]

Suppose that we have three elements [0, 1, 2] and that we union 0 and 1, and then 1 and 2.

When we union 0 and 1, let's suppose that 1 is the champion, so the array is [1, 1, 2]. Pictorially, we have:

What can happen after we union 1 and 2?

• For quick find, the answer 2,2,2 is possible, but this outcome is not possible for quick union, or weighted union.

  

• For quick union, the answer 1,2,2 is possible, but this outcome is not possible for quick find, or weighted union.

  

• For weighted union, the only possible outcome is 1,1,1. This outcome is possible under all three algorithms.