加权快速联合算法将如何实施？

Question

我目前正在参加普林斯顿算法课程（第 1 部分），它讨论了通过维护一个额外的数组 sz[i] 来计算根节点树中的对象数量来改进快速联合算法我，但它没有显示如何做到这一点。

应该在哪里以及如何实施该计数器？我试过在 root 方法中这样做，但我意识到它不会计算给定对象的子对象。

这是课程中给出的未更改代码：

public class QuickUnionUF {
    private int[] id;
    public QuickUnionUF(int N) {
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }
    private int root(int i) {
        while (i != id[i]) i = id[i];
        return i;
    }
    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }
    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

Answer 1

要执行加权联合，您需要知道每棵树的权重，因此制作并行数组wt[]，其中wt[k] 包含根为k 的树的大小。初始权重为 1.

将较小的树粘合到较大树的根并更新权重

public void union(int p, int q) {
    int i = root(p);
    int j = root(q);
    if wt[i] < wt[j] { 
        id[i] = j;
        wt[j] += wt[i] 
    }
    else {similar for j->i}
}

初始化

public class QuickUnionUF {
  private int[] id;
  private int[] wt;
  public QuickUnionUF(int N) {
    id = new int[N];
    wt = new int[N];
    for (int i = 0; i < N; i++) {
       id[i] = i;
       wt[i] = 1;
    }
  }

加权快速联合算法将如何实施？

How would the weighted quick-union Algorithm be implemented?

java

algorithm

counter

quick-union