定义

操作(合并 添加 删除)

斜堆(Skew heap)也叫自适应堆(self-adjusting heap)，是一种使用二叉树实现的堆状数据结构。

斜堆的优势是其合并的速度远远大于二叉堆。

斜堆是一种自适应的左偏树。

定义

斜堆可递归的定义如下：

只有一个元素的堆是斜堆。

两个斜堆通过斜堆的合并操作，得到的结果仍是斜堆。

操作

合并

我们可以用左偏树的合并算法实现两个斜堆的合并。

除此之外，还有一种非递归的算法。

分割每个堆。方法是从根节点开始，右子树与根节点分离，然后右子树以同样的方式分割。

最后得到一个树的集合，集合中的树的特点是：其根节点只有左子树或者没有子树。

对集合中的树，按照根节点的值从小到大排序。

从右到左，不断地合并最后两个子树，直到只剩下一棵树。

合并方法是：

如果倒数第二棵树有左子树，那么把左子树变为右子树。

把最后一棵树作为倒数第二棵树的左子树。 合并的时间复杂度分析 ：斜堆合并的摊还时间为O(logN)

定义：一个节点p，若其右子树的后裔数至少是p的后裔数的一般，则称p是重节点，否则称为轻节点

位势的选取：右路径上重节点的数目

证明：

令H1和H2为两个斜堆，节点数为N1和N2，右路径上轻重节点数目分别为l1和h1、 l2和h2

若合并代价定义为右路径上节点总数，则代价为l1+h1+l2+h2

合并操作的重要特性：右路径上的重节点肯定变为轻节点；而轻节点可能不变，也可能变为重节点。

考虑最坏情况，当然是所有轻节点均变为重节点

则位势（重节点数）的变化为l1+l2-h1-h2

平均摊还时间=代价+位势变化=2(l1+l2)

现在只需证明l1+l2=O(logN)

而l1和l2是原右路径上的轻节点数目，而轻节点左子树重、右子树轻，因此l1+l2至多为logN1+logN2，即O(logN)

而初始位势为0，始终非负，命题得证。

添加

添加元素，就是合并原斜堆和一个节点的斜堆。

删除

删除根节点，合并左右子树。