PrincetonAlgorithmsCoursePrograms/WeightedQuickUnionWithFindLargest.java at master · professorlevi/PrincetonAlgorithmsCoursePrograms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Created by Syed on 09-04-2018.
 */
public class WeightedQuickUnionWithFindLargest extends WeightedQuickUnion {
    int[] largest;
    public WeightedQuickUnionWithFindLargest(int n) {

        super(n);
        largest=id;

    }

    public void union(int p, int q) {
        int rootp = root(p);
        int rootq = root(q);
        if (rootp == rootq) return;
        int largestP = largest[rootp];
        int largestQ = largest[rootq];
        if (sz[rootp] < sz[rootq]) {
            id[rootp] = rootq;
            sz[rootq] += sz[rootp];

            if (largestP > largestQ)
                largest[rootq] = largestP;
        } else {
            id[rootq] = rootp;
            sz[rootp] += sz[rootq];

            if (largestQ > largestP)
                largest[rootp] = largestQ;
        }
    }

    public int find(int p) {
        return largest[root(p)];
    }

    public static void main(String a[]) {
        WeightedQuickUnionWithFindLargest canonicalQuickFind = new WeightedQuickUnionWithFindLargest(10);
        canonicalQuickFind.union(5, 2);
        canonicalQuickFind.union(2, 6);
        canonicalQuickFind.union(6, 9);

        System.out.print(canonicalQuickFind.find(6));
    }
}