Question

Using linked lists or a resizing array; develop a weighted quick-union implementation that removes the restriction on needing the number of objects ahead of time. Add a method newSite() to the API, which returns an int identifier.

Answer 1

Answer:

Step-by-step explanation:

package net.qiguang.algorithms.C1_Fundamentals.S5_CaseStudyUnionFind;

import java.util.Random;

/**

* 1.5.20 Dynamic growth.

* Using linked lists or a resizing array, develop a weighted quick-union implementation that

* removes the restriction on needing the number of objects ahead of time. Add a method newSite()

* to the API, which returns an int identifier

*/

public class Exercise_1_5_20 {

public static class WeightedQuickUnionUF {

private int[] parent; // parent[i] = parent of i

private int[] size; // size[i] = number of sites in subtree rooted at i

private int count; // number of components

int N; // number of items

public WeightedQuickUnionUF() {

N = 0;

count = 0;

parent = new int[4];

size = new int[4];

}

private void resize(int n) {

int[] parentCopy = new int[n];

int[] sizeCopy = new int[n];

for (int i = 0; i < count; i++) {

parentCopy[i] = parent[i];

sizeCopy[i] = size[i];

}

parent = parentCopy;

size = sizeCopy;

}

public int newSite() {

N++;

if (N == parent.length) resize(N * 2);

parent[N - 1] = N - 1;

size[N - 1] = 1;

return N - 1;

}

public int count() {

return count;

}

public int find(int p) {

// Now with path compression

validate(p);

int root = p;

while (root != parent[root]) {

root = parent[root];

}

while (p != root) {

int next = parent[p];

parent[p] = root;

p = next;

}

return p;

}

// validate that p is a valid index

private void validate(int p) {

if (p < 0 || p >= N) {

throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + (N - 1));

}

}

public boolean connected(int p, int q) {

return find(p) == find(q);

}

public void union(int p, int q) {

int rootP = find(p);

int rootQ = find(q);

if (rootP == rootQ) {

return;

}

// make smaller root point to larger one

if (size[rootP] < size[rootQ]) {

parent[rootP] = rootQ;

size[rootQ] += size[rootP];

} else {

parent[rootQ] = rootP;

size[rootP] += size[rootQ];

}

count--;

}

}

public static void main(String[] args) {

WeightedQuickUnionUF uf = new WeightedQuickUnionUF();

Random r = new Random();

for (int i = 0; i < 20; i++) {

System.out.printf("\n%2d", uf.newSite());

int p = r.nextInt(i+1);

int q = r.nextInt(i+1);

if (uf.connected(p, q)) continue;

uf.union(p, q);

System.out.printf("%5d-%d", p, q);

uf.union(r.nextInt(i+1), r.nextInt(i+1));

}

}

}