数据结构——启发式合并

· · 个人记录

一般情况下，合并两个数据结构的时间复杂度大于等于 O(n) ，效率 难以接受。启发式合并存在的意义，便是高效的合并若干个数据结构。

并查集的启发式合并

通常情况下，我们会这样写并查集的合并

void merge(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    f[x] = y;
}

在极端情况下，用这种写法实现的并查集会呈链状，时间复杂度将退化。这时我们有两种解决办法。

1、路径压缩

2、启发式合并

大多数情况下，路径压缩已经足够。

但是！

可持久化并查集。。。
无法使用路径压缩。。。
这时启发式合并便排上用场了
我们维护一个dep数组，dep_i表示以i为根的树的深度； 于是merge函数可以改成这样

void merge(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(dep[x] < dep[y]) f[x] = y;
    else if(dep[x] > dep[y]) f[y] = x;
    else f[x] = y, ++dep[y];
}

这样一来，size为n的树深度不超过\log n，于是所有操作复杂度都是O(\log n)。
在合并其他数据结构时，常常会使用并查集来维护每个数据结构是否已经被合并，从而保证效率。

线性数据结构的启发式合并

如果要合并的不是两个集合，而是两个栈、队列或是链表呢？
同样可以使用启发式合并。
设size表示数据结构的大小， 当要合并两个数据结构时，先判断大小，不难发现，将size小的数据结构暴力合并到size大的数据结构上一定比将size大的合并到size小的上更优。
于是我们每次都贪心的选择更优的操作，保证size小的数据结构在合并后size至少是原来的2倍。这样每个元素最多被遍历\log n次，因此启发式合并的均摊时间复杂度为O(\log n)。
伪代码如下

void merge(int x, int y) {
    if(已经合并) return;
    if(size[x] > size[y]) 将y合并到x;
    else 将x合并到y;
}

二叉堆的启发式合并

与上述线性数据结构的启发式合并几乎没有差异，而且Pairing Heap、Leftist Tree等可并堆编程复杂度并不比启发式合并高，效率却胜于启发式合并，所以二叉堆的启发式合并并不常见。

线段树的合并

线段树大体可分为两种，区间树和权值树。其中权值树可以用于维护一个有序可重集，因此也支持合并操作。

动态开点

普通线段树的空间复杂度为O(n)，若要将n可线段树合并，总的空间复杂度为O(n^2)，MLE妥妥的。
但是在大多数问题中，每个集合最初只有一个元素，在线段树内占用的空间为O(\log n)。如果开一棵满的线段树，就会有O(n-\log n)的空间被浪费。而动态开点仅保存使用到的空间，大大降低了时间复杂度。
对于在普通的权值线段树插入一个元素，通常这样实现

void insert(int o, int l, int r, int x) { // 当前结点为o,当前区间为[l, r],插入的数为x
    ++s[o].size;
    if(l == r) return;
    int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;
    if(x <= mid) insert(lc, l, mid, x);
    else insert(rc, mid + 1, r, x);
}

因为我们默认o的左子树为2o，右子树为2o+1，所以整棵线段树的空间复杂度为O(n)。我们可以从这儿入手，将不存在的结点编号设为0，更新时若结点存在就直接修改，若结点不存在就新增一个结点，再修改该结点。代码如下。

void insert(int &o, int l, int r, int x) { // 注意这里的o是引用
    if(!o) o = new_node();
    ++s[o].size;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(s[o].lc, l, mid, x);
    else insert(s[o].rc, mid + 1, r, x);

合并操作

设当前要把结点y合并到x上。
若x不存在，就直接把x赋值为y；
若y不存在，终止合并； 其余情况，合并x、y的信息后，递归合并其左右子树。
代码

void merge(int &x, int y) { // 将y合并到x上
    if (!x) { x = y; return; }
    if (!y) return;
    s[x].size += s[y].size;
    merge(s[x].lc, s[y].lc);
    merge(s[x].rc, s[y].rc);
}

时间复杂度

我们可以这样分析：
调用一次Merge函数的时间复杂度为O(1)，每调用一次，就会删掉一个点，所以合并的总代价为初始点数，即O(n\log n)。

注意：

合并两棵线段树的时间复杂度与其size之和有关，并非与size较小者有关。因此线段树合并中不存在启发式合并的概念。

平衡树的启发式合并

与线性数据结构的启发式合并类似，单次合并复杂度为O(n\log n)， 最多好吧\log n次，均摊下来复杂度为O(\log^2 n)。

但是！

有一种平衡树叫做Splay。。。
还有一种平衡树叫做Treap。。。
于是便有了。。。

Splay的启发式合并

注：以下部分内容摘自国家侯选队论文

首先，要引入一个概念。

Finger Search

一般情况下，在数据结构中查找某个元素的时间复杂度会表示成关于 n（即数据结构中的元素个数）的函数。设d(x, y)表示两个元素x, y在集合中的排名之差。在一些数据结构中，如果查找元素y时从节点x开始查找，那么时间复杂度就可以优化为关于d(x, y)的函数。
Finger Search指的就是在数据结构中从某些特定的节点（也就是“finger”）开始查找其他元素。假如被查找的元素与“finger”的排名距离很近，那么查询的效率就会有很大的提升。
例如在一个有序数组中，我们可以通过倍增来实现finger search，时间复杂度为O(\log (d(x, y)+1))。（此处以及下文的一些地方将 d(x, y) + 1 是为了避免\log 0的情况）。
而在平衡树中，我们可以将根结点视为一个Finger。于是便有了一个神奇的定理

Dynamic Finger Theorem

在一棵n个节点上的 Splay 上进行m次的插入、删除或 者查找操作的总时间为O(n+m+\Sigma_{i=1}^{m}(\log d_i+1))。其中d_i表示第i次操作的元素与第i−1 次操作的元素在该操作时的排名之差。第0次操作的元素可以视为初始的根节点。
别问我怎么证明。。。

如何实现

众所周知，Splay通过splay操作来保证均摊O(\log n)的时间复杂度，而splay操作提供了天然的Finger Search。 因此，在合并两棵Splay时，应该把较小的一棵按中序遍历插入较大的一棵。
那么这样做的时间复杂度是多少呢？
设当前要合并的两棵Splay为x和y。因为平衡树维护的是一个有序集合，所以，对这两棵Splay的合并就可以看做是对两个有序集合的合并。
为了方便，我们可以设x中排名为i的数是x_i，y中排名为i的数是y_i。那么合并之后的集合会是这个样子的：
{x_1,y_1,x_2,x_3,y_2......}
即将序列x,y归并后得到的序列。
不难发现，这两序列中的个元素对合并的时间复杂度至多会产生O(1)的贡献，所以合并两棵Splay的时间复杂度为O(n)。

综上所述，Splay启发式合并的均摊复杂度为O(\log n)。

Treap的启发式合并

还是有一个神奇的定理
两个元素 x, y 在 Treap 上的路径长度是期望O(\log (d(x, y) + 1))的。
仍然不要问我怎么证明。。。

如何实现

在Treap上找到结点x后，只需找到LCA(x,y)，便可找到y。可以向线段树那样维护每个结点所表示的区间，若当前区间已经包含y，就可以开始向下查找y了。

参考资料

黄学长的博客
《浅谈Splay与Treap的性质及其应用》董炜隽