Блог

В настоящее время я зачислен на курс алгоритмов Принстона (часть 1), и в нем говорится об улучшении алгоритма быстрого объединения путем сохранения дополнительного массива sz [i] для подсчета количества объектов в дереве с корнем i, но не показано, как это сделать.

Где и как предполагается реализовать этот счетчик? Я пытался сделать это в корневом методе, но понял, что он не будет учитывать дочерние элементы данного объекта.

Это неизмененный код, приведенный в курсе:

 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;
    }
}
  

Чтобы выполнить взвешенное объединение, вам нужно знать вес каждого дерева, поэтому создайте параллельный массив, 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;
    }
  }