左偏树

本文主要是介绍左偏树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

左偏树是一种比较简洁易懂的可并堆。

一般来说堆都是用来实现优先队列问题，也就是维护一个集合 \(H\)，支持：

1. \(\text{Insert}\) - 将一个元素 \(x\) 插入 \(H\)。

2. \(\text{Find-Min}\) - 求 \(H\) 中的最小元素。

3. \(\text{Delete-Min}\) - 从 \(H\) 中删除最小元素。

4. \(\text{Decrease-Key}\) - 降低 \(H\) 中某个指定元素的值。

5. \(\text{Meld}\) - 合并两个优先队列 \(H_1,H_2\)。

6. \(\text{Delete}\) - 从 \(H\) 中删除某个指定元素。

这里是以最小堆为例。

我们都知道 std::priority_queue 这个东西，它是以二叉堆来实现的，\(\text{Insert , Delete-Min , Decrease-Key}\) 都可以做到 \(O(\log n)\)。

二叉堆的时间复杂度是以树高来保证的，以维持其完全二叉树的形态来保证树高的 \(O(\log n)\)。

但是这玩意的局限性很大，难以做到较好的 \(\text{Meld}\)。

左偏树在这五个操作上都可以做到最坏 \(O(\log n)\) 的复杂度。

定义 & 性质

左偏树 \(T\) 是一棵二叉有序树。

任意一个节点 \(\alpha\in T\) 包含一个元素，为 \(val(\alpha)\)。

定义 "外节点" 为没有左儿子或右儿子的节点。

对于任意节点 \(\alpha\in T\)，定义 \(dist(\alpha)\) 为 \(\alpha\) 到以 \(\alpha\) 为根的子树中距离其最近的外节点所经过的边数。

\(T\) 的 \(dist\) 定义为根节点的 \(dist\)。外节点的 \(dist\) 为 \(0\)，空节点的 \(dist\) 为 \(-1\)。

性质 1. （堆性质）对于任意节点 \(\alpha\in T\)，设其左右儿子为 \(\beta_1,\beta_2\)，那么 \(val(\alpha)\leq val(\beta_1)\) 且 \(val(\alpha)\leq val(\beta_2)\)。

性质 2. （左偏性质）对于任意节点 \(\alpha\in T\)，设其左右儿子为 \(\beta_1,\beta_2\)，那么有 \(dist(\beta_1)\geq dist(\beta_2)\)。

引理 1. （左偏性质的推论）对于任意节点 \(\alpha\in T\)，设其左右儿子为 \(\beta_1,\beta_2\)，那么 \(dist(\alpha)=dist(\beta_2)+1\)。

引理 2. 一棵节点数为 \(n\) 的左偏树 \(T\) 的 \(dist=O(\log n)\)。

操作

\(\text{Meld}\)

合并两棵左偏树 \(T_1,T_2\)。

合并后的根为两者之中较小的根，

这篇关于左偏树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！