更新时间：2023-11-22 10:13
斜堆可递归的定义如下：
● 只有一个元素的堆是斜堆。
● 两个斜堆通过斜堆的合并操作，得到的结果仍是斜堆。
相比于左偏树
我们可以用左偏树的合并算法实现两个斜堆的合并。
除此之外，还有一种非递归的算法。
● 分割每个堆。方法是从根节点开始，右子树与根节点分离，然后右子树以同样的方式分割。
最后得到一个树的集合，集合中的树的特点是：其根节点只有左子树或者没有子树。
● 对集合中的树，按照根节点的值从小到大排序。
● 从右到左，不断地合并最后两个子树，直到只剩下一棵树。
合并方法是：
● 如果倒数第二棵树有左子树，那么把左子树变为右子树。
● 把最后一棵树作为倒数第二棵树的左子树。 合并的时间复杂度分析 ：斜堆合并的摊还时间为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，始终非负，命题得证。
添加元素，就是合并原斜堆和一个节点的斜堆。同左偏树。
删除根节点，合并左右子树。同左偏树。