Weighted quick union
The weighted quick union, is a quick union variant that keeps track of the size of each tree so it can always connect the smaller tree to the larger one so avoiding worst cases. The tree height is substantially smaller guaranteeing logarithmic performance.
The algorithm introduces a new element-indexed vector to hold the total nodes count (szs) which is used by the union function to link the root of the smaller tree size to the root of the larger one:
#[derive(Debug)]
/// WeightedQuickUnion data structure for solving the dynamic connectivity problem.
pub struct WeightedQuickUnion {
/// Keeps the number of connected components
count: usize,
/// An element-indexed vector to represent the components. The name of one of the elements in a
/// component will be used as the component identifier.
ids: Vec<usize>,
/// An element-indexed vector to hold node counts.
szs: Vec<usize>,
}The find function remains the same but now the union function checks the sizes of the root elements in order to connect the smaller tree to the larger one:
impl UnionFind for WeightedQuickUnion {
/// Merges two components if the two elements are in different components.
fn union(&mut self, p: usize, q: usize) {
let i = self.find(p);
let j = self.find(q);
if i != j {
if self.szs[i] < self.szs[j] {
self.ids[i] = j;
self.szs[j] += self.szs[i];
} else {
self.ids[j] = i;
self.szs[i] += self.szs[j];
}
self.count -= 1;
}
}
/// Returns the component identifier for a given element.
fn find(&mut self, mut i: usize) -> usize {
while i != self.ids[i] {
i = self.ids[i];
}
i
}
/// Returns the number of components.
fn components(&self) -> usize {
self.count
}
}The size of a tree is the number of nodes. The depth of a node tree is the number of hops to its root and the height of a tree is the maximum depth among its nodes.
Even for the worst cases, where the sizes of the trees to union are the equal the performance of the algorithm is logarithmic. The tree structure has a property that the depth of any node is at most . A detailed explanation of the algorithm process can be found in the unit test:
#[test]
fn test_weighted_quick_union() {
let mut alg = WeightedQuickUnion::new(10);
// Initial state: all elements roots are themselves and their root sizes are 1. The total
// components are 10.
let mut expected_find_pos = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
//
// sizes: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
assert_eq!(alg.components(), 10);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 4 and 3, Both elements are roots and have the same size so q(3) is connected to the
// root of p(4) and its size is added to the size of the root of p. The total components are 9.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 4, 4, 5, 6, 7, 8, 9];
// ^ ^
// sizes: [1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
// ^
alg.union(4, 3);
assert_eq!(alg.components(), 9);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 3 and 8, their roots are 4 and 8 respectively and their root sizes are 2 and 1, the
// size of the root of p(4) is greater than the size of the root of q (8) so the root of q(8)
// gets connected to the root of p(4) and its size gets added to the size of the root of p(4).
// The total components are 8.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 4, 4, 5, 6, 7, 4, 9];
// ^ ^
// sizes: [1, 1, 1, 1, 3, 1, 1, 1, 1, 1]
// ^
alg.union(3, 8);
assert_eq!(alg.components(), 8);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 6 and 5, their roots are themselves and their root sizes is 1, so q(5) is connected
// to p(6) and the size of 6 is incremented by the size of 5. The total components are 7.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 4, 4, 6, 6, 7, 4, 9];
// ^ ^
// sizes: [1, 1, 1, 1, 3, 1, 2, 1, 1, 1]
// ^
alg.union(6, 5);
assert_eq!(alg.components(), 7);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 9 and 4, their roots are themselves and their root sizes are 1 and 3 respectively so
// the root of p(9) is connected to the root of q(4) and its size is incremented by the size of
// the root of p(9). The total components are 6.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 4, 4, 6, 6, 7, 4, 4];
// ^ ^
// sizes: [1, 1, 1, 1, 4, 1, 2, 1, 1, 1]
// ^
alg.union(9, 4);
assert_eq!(alg.components(), 6);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 2 and 1, their roots are themselves and their root sizes are 1 so q(1) is connected to
// p(2) and the its size is incremented by one. The total components are 5.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 2, 2, 4, 4, 6, 6, 7, 4, 4];
// ^ ^
// sizes: [1, 1, 2, 1, 4, 1, 2, 1, 1, 1]
// ^
alg.union(2, 1);
assert_eq!(alg.components(), 5);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 8 and 9, their roots are the same: 4 so nothing else is needed.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 2, 2, 4, 4, 6, 6, 7, 4, 4];
// ^ ^
// sizes: [1, 1, 2, 1, 4, 1, 2, 1, 1, 1]
//
alg.union(8, 9);
assert_eq!(alg.components(), 5);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 5 and 0, their roots are 6 and 0 respectively and their root sizes 2 and 1 so the root
// of q(0) is connected to the root of p(6) and its size is incremented by the size of the root
// of q which is 1. The total components are 4.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [6, 2, 2, 4, 4, 6, 6, 7, 4, 4];
// ^ ^
// sizes: [1, 1, 2, 1, 4, 1, 3, 1, 1, 1]
// ^
alg.union(5, 0);
assert_eq!(alg.components(), 4);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 7 and 2, both are roots but their sizes are 1 and 2 respectively so the root of p(7)
// is connected to q(2) and its size is incremented by the size of the root of p. The total
// components are 3.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [6, 2, 2, 4, 4, 6, 6, 2, 4, 4];
// ^ ^
// sizes: [1, 1, 3, 1, 4, 1, 3, 1, 1, 1]
// ^
alg.union(7, 2);
assert_eq!(alg.components(), 3);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 6 and 1, their roots are 6 and 2 and their root sizes are the same so the
// root of q(1) which is 2 is connected to the root of p(6) which is 6 and its size is
// incremented after summing up the size of the root of q(1) which is 3. The total components
// are 2.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [6, 2, 6, 4, 4, 6, 6, 2, 4, 4];
// ^ ^ ^
// sizes: [1, 1, 3, 1, 4, 1, 6, 1, 1, 1]
// ^
alg.union(6, 1);
assert_eq!(alg.components(), 2);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 1 and 0, their roots are the same 6 so nothing else is needed.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [6, 2, 6, 4, 4, 6, 6, 2, 4, 4];
// ^ ^
// sizes: [1, 1, 3, 1, 4, 1, 6, 1, 1, 1]
//
alg.union(1, 0);
assert_eq!(alg.components(), 2);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 6 and 7, like in the last iteration their roots are the same 6 so nothing else is
// needed.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [6, 2, 6, 4, 4, 6, 6, 2, 4, 4];
// ^ ^
// sizes: [1, 1, 3, 1, 4, 1, 6, 1, 1, 1]
alg.union(6, 7);
assert_eq!(alg.components(), 2);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
}The full source code can be found here.