Before the order

In Walloran, there were two opposing camps: Noxas and Demacia. The same camp can not attack each other, so before they PK, have to confirm the identity of the other party, to avoid causing an own incident. In the beginning, they will carry the same token, every time everyone PK with the token to compare, if it is the same camp, everyone will be minor. It is when is the fastest, with a token out each other can directly, but at the time of merger alliance more troublesome, such as galen jia wen prince their small groups joined DE Marcia, so they are the people in the team in the token, if xenzhao first joined the firm team, then add DE Marcia, then he will have to change two tokens. Every time two small teams make an alliance, there is always a force that needs to change the token operation internally to ensure the unity of all the tokens after the alliance, which is the centralized Quick-find method. The advantage of this method is that when confirming whether the two parties are in the same camp, it can be determined most quickly, because the token of the same camp is always the same.

But at this rate, the underlings of the lineup might have to change tokens once a day. Gallio is a bad-tempered guy, and after three more days and five token changes he finally broke down and said, “I’ll take the token I have.” So the officers talked it over and came up with another method. That is, everyone takes care of their soldiers, and then asks the leader of the other side before PK. If you don’t know them, let the leader ask their leader. In this way, when asked about the highest leader, the highest leader of the same camp is always the same, and there can only be one king in each camp. In this way, the boys are finally free from the trouble of changing tokens frequently. Every soldier, except when he first joined the army, was always under the leadership of the officer. This is the quick-union method of the parallel lookup set. The benefits of this approach is in a superior, each soldier just need to confirm at the time of merger can be directly induces the second army generals to the first general in the army, his men soldiers don’t need to do any change, can be the fastest to merge, but when judging whether the same camp, need from the lower layers to up cycle, Ask the highest officer, the king, to make sure they are the same king.

But this is also bad, that is, before each PK have to go through a round of questioning, such as an hour after both sides are finished asking belly hungry. So the officials thought of another way, is that after the first inquiry, at each level of inquiry, the superior feedback back who is the king. They wrote down their king. So the next PK before only need to ask the record of the king, he is still the highest leadership. Why do I need this step? Because until we can merge factions, there can only be one king on each side, and the other side becomes the king’s general. This step is called path compression in parallel lookup sets and is the most commonly used union-find.

Introduction to the

In the above scenario, we can use Union Find to record the relationship between factions in our code world. A parallel lookup set is a data structure used to manage groups. It has two operations:

(1) Query whether element A and element B are the same group

(2) Merge elements A and b into the same group.

implementation

QuickFind

class QuickFind {
  constructor(n) {
    // In the beginning, everyone's superior is themselves, we have the same index to identify the position of the superior
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find someone's supervisor
  find(index) {
    return this.parent[index];
  }

  // Merge the two armies. Here we use army 1 as the main force
  merge(index1, index2) {
    // Find the tokens for army 1 and Army 2
    let p1 = this.find(index1), p2 = this.find(index2);

    // Replace all army 2 tokens with Army 1 tokens
    this.parent.forEach((item, index) = > {
       if (this.find(index) === p2) {
        this.parent[index] = p1; }}); }}Copy the code

QuickUnion

class QuickUnion {
  constructor(n) {
    // In the beginning, everyone's superior is themselves, we have the same index to identify the position of the superior
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find someone's top boss
  find(index) {
    // Top officer means he is his own superior
    if (this.parent[index] === index) return index;

    // If not, go up
    return this.find(this.parent[index]);
  }

  // Merge the two armies. Here we have army 1 as the main force, and the leader of army 2 is now the eldest brother
  merge(index1, index2) {
    let p1 = this.find(index1), p2 = this.find(index2);
    if(p1 ! == p2) {this.parent[p2] = p1; }}}Copy the code

UnionFind

class UnionFind {
  constructor(n) {
    // In the beginning, everyone's superior is themselves, we have the same index to identify the position of the superior
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find someone's top boss
  find(index) {
    // Top officer means he is his own superior
    if (this.parent[index] === index) return index;

    // If not, go up

    // Path compression
    this.parent[index] = this.find(this.parent[index]);
    
    return this.parent[index];
  }

  // Merge the two armies. Here we have army 1 as the main force, and the leader of army 2 is now the eldest brother
  merge(index1, index2) {
    let p1 = this.find(index1), p2 = this.find(index2);
    if(p1 ! == p2) {this.parent[p2] = p1; }}}Copy the code

Code to streamline

class UnionFind {
  constructor(n) {
    // In the beginning, everyone's superior is themselves, we have the same index to identify the position of the superior
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find someone's top boss
  find(index) {
    // The highest officer means he is his superior, otherwise the recursion is upward
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Merge the two armies. Here we have army 1 as the main force, and the leader of army 2 is now the eldest brother
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

At this point, we’re done writing the code to look up the set structure, but that doesn’t mean there’s no room for optimization. We can judge the number of nodes in the two structures to be merged during the merging operation and merge the tree with fewer nodes into the tree with more nodes. However, the optimization effect of this step is not very obvious, and will increase our mental burden. I’m not going to go through them.