Quick-union sample analysis

In the last test verification, it can be concluded that Quick-Union has some advantages over Quick-find algorithm, but the performance of Quick-Union algorithm is not very good in the case of the increase of connected data sets. It is still necessary to analyze the performance of Quick-Union algorithm in different data sets.

The optimal conditions

The optimal situation is to avoid the disadvantage of Quick-union and find component identifiers within O(1) time. For example, if the connected data set is as follows:

The serial number p q
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
0 0 9

Results after merger:

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 1 2 3 4 5 6 7 8 9 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 0 0 0 0 0 0 0 0 0Copy the code

Into a graphical

Undoubtedly, it can be intuitively felt that in each merging operation, new components are directly merged under the identifier of component 0. Components 1 to 9 are horizontal mechanisms, and each component can find its corresponding identifier through a search. This means that in special data cases, quick-union can achieve the same effect as Quick-find without traversal!

Worst case

In the worst case, there is as much depth as there are components, so the time complexity of each find operation is order (n), so let me give you an example. (Quick-Union’s code has one change for illustrative purposes.)

@override void union(int p, int q) {int pId = find(p); Int qId = find(q); If (pId == qId) return; P id[pId] = qId; // Each merge reduces count--; }Copy the code
The serial number p q
0 0 1
0 1 2
0 2 3
0 3 4
0 4 5
0 5 6
0 6 7
0 7 8
0 8 9

Results after merger:

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 1 2 3 4 5 6 7 8 9 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 1 2 3 4 5 6 7 8 9 9 -------------------------------Copy the code

Into a graphical

It can also be seen intuitively that the serious imbalance of parallel search sets at this time will greatly reduce the execution efficiency of the algorithm.

In view of this situation, the purpose of optimization has become very clear, we should try to maintain the balance of the class tree, try to avoid this imbalance situation, naturally can improve the performance of the algorithm.

Weighted quick – union

From the worst sample, we can see that this extremely unbalanced linked list-style tree is formed because each operation merges a large tree into a small one. For example, on the last connected merge p=8,q=9, we performed the following operation

We are in the weighted case, after the merger formed

But what we’re hoping for is

So, if we have a variable to compare the weights of the two components to be merged, and we always merge the low-weight component into the high-weight component, then this extreme tilted tree should be improved.

After the above verification and analysis, let’s analyze the processing steps of weighted Quick-union

  • Add a member attribute to quick that identifies the weight of the component
  • In the merging operation, it is no longer simply to assign one component to another component, but to carry out a weight comparison, and merge the components with small weight into the components with large weight.

Look directly at the code

package com.zt; Public class WeightedQuickUnionUnionFind extends UnionFind {/ / component weight array, the array of values that represent the current number of components in the component private int [] weightArr; public WeightedQuickUnionUnionFind(int n) { super(n); weightArr = new int[n]; For (int I = 0; int I = 0; i < weightArr.length; i++) { weightArr[i] = 1; }} @override void union(int p, int q) {int pId = find(p); Int qId = find(q); If (pId == qId) return; If (weightArr[p] < weightArr[q]) {id[p] = q; weightArr[q] += weightArr[p]; } else { id[q] = p; weightArr[p] += weightArr[q]; } // Each merge reduces a different component group count--; } @override int find(int p) {// Override int find(int p) { =id[p]) p = id[p]; return p; }}Copy the code

Verify the effect of

Verify the combined worst data set results again

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 1 1 0 0 1 2 2 2, 3, 3, 3, 4, 4, 4, 5 5 5 6 June 6 July 7 7 8 8 8 9 9 0 0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 1 2 3 4 5 6 7 8 9 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 0 0 0 0 0 0 0 0 0 -------------------------------Copy the code

You can see that after weighting, the Quick-Union becomes a flat tree, optimizing the result.

Random data set

Because the data is special, we randomly generate a set of sample data to compare again.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 5 4 1 9 5 2 4 7, 3, 4, 5, 4, 5 5 1 0 6 1 7 6 7 8 1 2 September 1 -------------------------------Copy the code

Unweighted results

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 1 2 3 4 5 6 7 8 9 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 2 0, 2, 3, 7, 4 0 1 August 4 -------------------------------Copy the code

The weighted results

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 0 1 2 3 4 5 6 7 8 9 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 5 5 5 3 5 6 August 5 -------------------------------Copy the code

conclusion

The weighted quick-union can obviously optimize the disadvantage of Quick-union, and the depth of the tree can be controlled at the log(n) level, or even better. The weighted union search set has undergone further evolution.

Looking forward to

Weighted Quick-union is not optimized yet. Is there a way to make quick-union only have one layer? Upgrade from O(log(n)) time complexity to O(1)? Let’s explore that next time.