跳到主要内容

模板代码

如何用数组实现优先队列？​

  • 结构: 完全二叉树按层序存储在数组中, 索引 ii 的父节点为 (i-1) >> 1, 左右子节点为 2i+1 与 2i+2;
  • 比较器: 构造时传入 cmp, 用 cmp(子, 父) 决定是否需要交换, 从而支持大顶堆与小顶堆;
  • 入队: 追加到数组尾部, 然后向上与父节点比较并交换, 直到满足堆序;
  • 出队: 交换堆顶与尾部元素, 弹出尾部, 再让新堆顶向下与较小的子节点交换, 直到满足堆序;
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) {
      const 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;
    let exchange = index * 2 + 1;
    while (exchange < length) {
      const 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() {
    return this.size() ? this.container[0] : null;
  }
}
  • 复杂度: push 与 pop 均为 O(log⁡n)O(\log n), peek 为 O(1)O(1);

如何用数组实现并查集？​

  • 结构: fa[i] 记录节点 ii 的父节点, 根节点满足 fa[i] === i;
  • 查找: 沿父指针上溯到根, 顺路把路径上的节点直接挂到祖父节点, 即路径压缩;
  • 合并: 把一棵树的根挂到另一棵树的根下;
  • 判定: 两个节点根相同即连通;
class UnionFind {
  constructor(n) {
    this.fa = Array.from({ length: n }, (_, 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) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) this.fa[rootX] = rootY;
  }

  isConnected(x, y) {
    return this.find(x) === this.find(y);
  }
}
  • 复杂度: 单次操作均摊接近 O(1)O(1);
  • 易错点: union 必须挂接两个根节点, 直接写 fa[x] = y 会破坏树结构;
  • 关联: 并查集在树相关题目中的应用见同 collection 的「树」目录;