数据结构：左偏堆
左偏堆简介
又称左偏树、左倾堆，这么多名字都带个左，那就是因为它向左倾斜，和二叉堆一样都是一种优先队列实现方式。
左偏堆的一些定义
零距离（Null Path Length）：从一个节点到空节点的距离，简称NPL（这个理解看下图就立刻明白了）
image
左偏堆的性质
- [性质1] 节点的键值小于或等于它的左右子节点的键值。
- [性质2] 节点的左孩子的NPL >= 右孩子的NPL。
- [性质3] 节点的NPL = 它的右孩子的NPL + 1。
所有的操作就围绕着这三个性质，这是左偏树的所有操作的依据
合并
合并操作步骤
-
如果两个空左倾堆合并，返回为空
-
一个空左倾堆和非空左倾堆合并，返回非空左倾堆
-
两个非空左倾堆合并
第一步：比较两个堆的根节点，取较小根作为新的根节点，将较小堆的右孩子和较大的堆合并作为新根节点的右孩子
第二部：如果新堆的右孩子的NPL>左孩子的NPL,交换左右孩子，更新新堆的根节点的NPL
图文讲解
合并是左偏树的精髓，插入，删除都要用到合并，这一节咱们用图来展示合并的过程
image
<center>比较两个堆的根元素大小（20，42），选择小的作为主堆</center>
image
<center>选择小堆的右子树（以72为根的子树）和以42为根的树进行比较</center>
image
<center>42<72,交换以42为根的树和以72为根的树的位置</center>
image
<center>继续选择右子树，重复上面的动作</center>
image
<center>比较86和72</center>
image
<center>交换位置</center>
image
<center>比较79和86</center>
image
<center>将86作为79的右子树</center>
image
<center>更新86的npl</center>
image
<center>继续更新，64的右子树的npl大于左子树的npl</center>
image
<center>更新npl,交换64的左右子树</center>
image
<center>更新npl,20的右子树npl大于左子树的npl</center>
image
<center>交换20的左右子树，20是整个堆的根节点到此结束</center>
合并代码实现
public Node merge(Node xHeap,Node yHeap){
//任何一个堆为空，都将另一个堆作为主堆
if(xHeap == null){
return yHeap;
}
if(yHeap == null){
return xHeap;
}
//xheap作为主树，选择key小的作为主堆
if(xHeap.getValue()>yHeap.getValue()){
Node tem =xHeap;
xHeap = yHeap;
yHeap =tem;
}
//主堆的右子树是是主堆的右子树和yHeap合并的结果
xHeap.setRight(merge(xHeap.getRight(),yHeap));
if(xHeap.getLeft()==null||xHeap.getLeft().getNpl()<xHeap.getRight().getNpl()) {
Node left = xHeap.getLeft();
Node right =xHeap.getRight();
xHeap.setRight(left);
xHeap.setLeft(right);
}
xHeap.updateNpl();
return xHeap;
}
public void updateNpl(){
if(left ==null||right ==null){
npl = 0;
}
npl = right.getNpl()+1;
}
删除
这里的删除是指的是删除最小值（最大值），也就是根节点。我们只需将根节点的左右节点合并就可以了
//删除，删除的是最小值，也就是根节点
public boolean remove(){
if(root == null){
return false;
}
if(root.getLeft()!=null){
root.getLeft().setParent(null);
}
if(root.getRight()!=null){
root.getRight().setParent(null);
}
root= merge(root.getLeft(),root.getRight());
return true;
}
插入
插入操作可以看做一个只有一个节点的左偏树和另一棵树合并
public void inserNode(int key){
Node node = createNode(key);
root = merge(root,node);
}
一个拓展延伸 —— 斜堆
斜堆是左偏树的一个变种，差异就是斜堆没有零距离的概念，合并后不用判断NPL，直接交换左右孩子，也就是去掉NPL判断。个人感觉斜堆和左偏堆是一个东西，只是在保持相对平衡上的策略有所差异，没什么实质的区别。
public Node merge(Node xHeap,Node yHeap){
if(xHeap == null){
return yHeap;
}
if(yHeap == null){
return xHeap;
}
//xheap作为主树
if(xHeap.getValue()>yHeap.getValue()){
Node tem =xHeap;
xHeap = yHeap;
yHeap =tem;
}
xHeap.setRight(merge(xHeap.getRight(),yHeap));
if(xHeap.getLeft()==null) {//差异就在这一行
Node left = xHeap.getLeft();
Node right =xHeap.getRight();
xHeap.setRight(left);
xHeap.setLeft(right);
}
xHeap.updateNpl();
return xHeap;
}
总结
左偏堆是可合并堆的一种堆，是实现优先队列的一种方式，左偏树的灵魂就是合并。如果不牵扯到合并，使用二叉堆就很方便，效率很高，如果会有合并的操作，左偏树是一种不错的选择。
