模板代码

优先队列

class Heap {
  constructor(cmp) {
    this.container = [];
    this.cmp = cmp;
  }

  push(data) {
    const { container, cmp } = this;
    container.push(data);
    let index = this.size() - 1;
    while (index) {
      let parent = (index - 1) >> 1;
      if (!cmp(container[index], container[parent])) {
        return;
      }
      [container[index], container[parent]] = [
        container[parent],
        container[index],
      ];
      index = parent;
    }
  }

  pop() {
    const { container, cmp } = this;
    if (!this.size()) {
      return null;
    }
    [container[0], container[container.length - 1]] = [
      container[container.length - 1],
      container[0],
    ];
    const res = container.pop();
    const length = this.size();
    let index = 0,
      exchange = index * 2 + 1;
    while (exchange < length) {
      let right = index * 2 + 2;
      if (right < length && cmp(container[right], container[exchange])) {
        exchange = right;
      }
      if (!cmp(container[exchange], container[index])) {
        break;
      }
      [container[index], container[exchange]] = [
        container[exchange],
        container[index],
      ];
      index = exchange;
      exchange = index * 2 + 1;
    }
    return res;
  }

  size() {
    return this.container.length;
  }

  peek() {
    if (this.size()) return this.container[0];
    return null;
  }
}

并查集

class UnionFind {
  constructor(n) {
    this.fa = new Array(n).map((_, index) => index);
  }

  find(x) {
    while (this.fa[x] !== x) {
      this.fa[x] = this.fa[this.fa[x]];
      x = this.fa[x];
    }
    return x;
  }

  union(x, y) {
    indexX = this.fa.indexOf(x);
    indexY = this.fa.indexOf(y);
    if (indexX !== indexY) {
      this.fa[x] = indexY;
    }
  }

  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }
}