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 (sz[rootP] < sz[rootQ]) { id[rootP] = rootQ; sz[rootQ] += sz[rootP]; }
else { id[rootQ] = rootP; sz[rootP] += sz[rootQ]; }
count--;
}
2. Priority queue implemented by binary heap:
public Key delMin() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
exch(1, N);
Key min = pq[N--];
sink(1);
pq[N+1] = null; // avoid loitering and help with garbage collection
if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2);
assert isMinHeap();
return min;
}
3. Heap sort:
public static void sort(Comparable[] pq) {
int N = pq.length;
for (int k = N/2; k >= 1; k--)
sink(pq, k, N);
while (N > 1) {
exch(pq, 1, N--);
sink(pq, 1, N);
}
}
4. Randomized queue:
public Item dequeue() {
if (size <= 0) {
throw new NoSuchElementException("Tried to dequeue an empty queue.");
}
int index = StdRandom.uniform(size);
Item item = items[index];
items[index] = items[--size];
items[size + 1] = null;
if (size > ORIG_CAPACITY && size < capacity / 4) {
resize(capacity / 2);
}
return item;
}
5. 8-puzzle:
The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the taxicab(or manhanttan) distances between each block and its position in the goal configuration
// return sum of Manhattan distances between blocks and goal
public int manhattan() {
int manhattan = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int current = blocks[i][j];
if (current == 0) continue; // skip blank square.
if (current != (i * N + j + 1)) {
manhattan += Math.abs((current -1 ) / N - i) + Math.abs((current - 1) % N - j);
}
}
}
return manhattan;
}
