斜堆

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

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

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

定义斜堆可递归的定义如下：

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

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

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

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

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

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

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

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

合并方法是：

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

● 把最后一棵树作为倒数第二棵树的左子树。

添加添加元素，就是合并原斜堆和一个节点的斜堆。删除删除根节点，合并左右子树。

[1][2]