偏斜的艺术,左偏树与斜堆(数据结构之可并堆)


简介

左偏树是一种树形数据结构,更准确地说,是一种堆形数据结构,因此又叫左偏堆(左堆)。

什么叫“堆形”?简单来讲,就是满足如下性质的一种数据结构。

堆性:一个树形数据结构,满足其子节点和父节点的键值具有某种关系这一性质。

常见的堆有大根堆、小根堆等,这名字也非常形象——可以想象一个类似汉诺塔的堆状物,或是一些集装箱叠起来的东西,一般人们都习惯把大箱子放在小箱子上面“堆”起来。

左偏树是一种特殊的堆,它在堆的基础上多了“左偏性”,这正是它保证合并复杂度的关键所在。而斜堆是左偏堆的一个变种,它省掉了左偏堆的“交换左右子树”的操作,并且在均摊意义下仍能保证复杂度正确。

下面文章主要讲左偏堆,斜堆将在最后部分作为拓展引出。


性质

在提到左偏性之前,需要引入两个重要的概念:外节点和距离。

外节点:左偏树中儿子数小于2的节点。

距离:对于左偏树上一个点,它的距离定义为到离他最近的外节点所要经过的边数。特别地,外节点距离为0,空节点距离为-1。

基于此引入左偏树的基本性质。

左偏性:对于左偏树上任何一个点,$$dis_{leftson} \ge dis_{rightson}$$。

上图是个左偏树的实例,图中黑色表示键值,红色表示距离,以大根堆为例。

按照这个基本性质,我们很容易得到一些推论。

推论1:$$dis_{node}=dis_{rightson} + 1$$

这是因为右儿子距离总是较小的,按“最近”这个定义可以很容易看出来。

推论2:$$dis_{node} \le \log_{2} (N+1)-1$$

其中N是节点总数,并且当且仅当其为完全二叉树时,并且node为根节点时取等。

我们可以只考虑根节点,因为如果存在子节点的距离更大,我们可以递归地考虑那个子树,显然此时 N 更小,不等式更强了。

而假设根节点的距离为d,也即一直往根节点右手走有d这么长,那么点最少的情况一定是完全二叉树,此时点数为 $$2^{d+1}-1$$

因此得证。


时间复杂度

由于左偏树主要优势在于合并,而添加节点、删除节点都可以通过合并来达到(事实上,可并堆的插入、删除都可以这样归结为合并),因此这里只考虑合并这一操作。

左偏堆的合并操作:

  1. 记根较小的树为 u,则递归合并:\(merge(u, v) = merge(v, u \rightarrow rightSon)\)。
  2. 递归终止:当待合并两树中有一者为空时,直接返回非空。
  3. 合并后:更新左右子树的 \(dis\),如果违反了左偏性,交换左右子树。

由于每次合并都取一个树的右子树,由推论 2 知道每次会使一个树根的距离值减1,因此递归深度的级别为 \(\log\ n\)。

因此合并操作的时间复杂度级别为 \(O(\log\ n)\)。


斜堆

待更新,需要使用势能摊还法证明,作者需要学习一下...

声明:没有风会经过的旅店|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 偏斜的艺术,左偏树与斜堆(数据结构之可并堆)


如飞蛾之赴火,岂焚身之可吝。