C48fcabbedb034cac61f0a083aa76c6a
并查集秩优化

并查集秩优化

这些文章转自公众号:《让技术一瓜共食》,id:tech_gua,关注公众号可免费阅读这些文章。小专栏有独家的习题集和习题解答,会帮你掌握这些知识点。

上一次我们说到在传统的并查集算法中,由于没有对森林中的多叉树做任何的处理,所以会出现多叉树的深度无法控制,造成了在 find 方法进行查询的时候,随着大量的 union 操作调用,造成了复杂度的线性上升。最后多叉树变成了一个类似于线性表的结构,就缺失了原有数据结构的特性。

这种问题是由数据量的增多和数据结构执行操作的增多造成的,也是更多优秀的高级数据结构出现的原因。我们称这种变化叫做树的退化。那么对于树的退化问题,如果并查集算法不做任何的改进,最终也就失去了高效的特点,那么其时间开销也就于多个数组来处理集合问题旗鼓相当了。

定义 Rank

为了解决树的退化问题,我们引入一个 Rank 的秩概念:

  • 对于每棵树,记录这棵树的高度 Rank

进而,当我们执行 union 操作来合并两棵树时,如果两棵树的 Rank 不同,那么从 Rank 小的向 Rank 大的连边。

如此,我们就解决了由于 union 操作而造成了逐渐退化的情况。

路径压缩

此外,当点与点、点于链进行 union 操作的时候,由于都是直链,所以不存在 Rank 的差异化问题,在 union 之后也是一条直链。假设一条链的长度是 N,那么在一次 find 查询的过程中很有可能复杂度也是 O(N)。

这种情况通过路径压缩,便可以使并查集更加高效。对于每个节点,一旦向上走到了一次根节点,就把这个点与父节点的边改为直接连向根。

多点压缩

在此之上,不仅仅是所查询的节点,在查询过程中向上经过的所有节点,都改为直接连到跟上。这样再次查询这些节点时,就可以很快知道其根是谁。

增加优化后的代码实现

下面是并查集实现的例子。在例中,我们用编号代表每个元素,数组 par 表示的是父亲的编号,par[x] = x 时,x是所在的树的根。

```cpp

include

using namespace std;

const int MAX_N = (int)1e6+5;

int par[MAX_N];
int Rank[MAX_N];

// 初始化 n 个元素
void init(int n) {
memset(par, -1, sizeof(par));
for (int i = 0; i < n; ++ i) {
par[i] = i;
Rank[i] = 0;

top Created with Sketch.