可持久化可并堆

可持久化可并堆一般用于求解 短路问题。

如果一种可并堆的时间复杂度不是均摊的，那么它在可持久化后单次操作的时间复杂度就保证是 的，即不会因为特殊数据而使复杂度退化。

可持久化左偏树

在学习本内容前，请先了解

左偏树 的相关内容。

过程

回顾左偏树的合并过程，假设我们要合并分别以 为根节点的两棵左偏树，且维护的左偏树满足小根堆的性质：

1. 如果 中有结点为空，返回 。

2. 选择 两结点中权值更小的结点，作为合并后左偏树的根。

3. 递归合并 的右子树与 ，将合并后的根节点作为 的右儿子。

4. 维护当前合并后左偏树的左偏性质，维护 dist 值，返回选择的根节点。

由于每次递归都会使 dist[x]+dist[y] 减少一，而 dist[x] 是 的，一次最多只会修改 个结点，所以这样做的时间复杂度是 的。

可持久化要求保留历史信息，使得之后能够访问之前的版本。要将左偏树可持久化，就要将其沿途修改的路径复制一遍。

所以可持久化左偏树的合并过程是这样的：

1. 如果 中有结点为空，返回 。

2. 选择 两结点中权值更小的结点，新建该结点的一个复制 ，作为合并后左偏树的根。

3. 递归合并 的右子树与 ，将合并后的根节点作为 的右儿子。

4. 维护以 为根的左偏树的左偏性质，维护其 dist 值，返回 。

由于左偏树一次最多只会修改并新建 个结点，设操作次数为 ，则可持久化左偏树的时间复杂度和空间复杂度均为 。

参考实现