左式堆（Leftist Heaps)又称作最左堆、左倾堆。左式堆作为堆的一种，保留了堆的一些属性。
第1，左式堆仍然以二叉树的形式构建；
第2，左式堆的任意结点的值比其子树任意结点值均小（最小堆的特性）。但和一般的二叉堆不同，左式堆不再是一棵完全二叉树（Complete tree)，而且是一棵极不平衡的树。
package com.wpr.collection; /**
* 左式堆：二叉堆缺点，首先，只能查找最小元素；其次，将两个堆合并的操作很麻烦
* 注意：所有支持有效合并的高级数据结构都需要使用链式数据结构
*
* 定义：零路径长（null path length）npl表示从节点X到一个不具有两个儿子的节点的最短路径的长
*
* @author wpr
*
*/
public class LeftHeap<AnyType extends Comparable<? super AnyType>> { private Node<AnyType> root; public LeftHeap() {
root = null;
}
private static class Node<AnyType> {
AnyType element;
Node<AnyType> left;
Node<AnyType> right;
int npl;
public Node(AnyType element) {
this(element,null,null);
}
public Node(AnyType element, Node<AnyType> left, Node<AnyType> right) {
this.element = element;
this.left = left;
this.right = right;
this.npl =0 ;
}
}
/**
* @param x
*/
public void merge(LeftHeap<AnyType> x){
if(this == x)
return ; root = merge(root,x.root);
}
/**
* 插入一个新元素
* @param x
*/
public void insert(AnyType x){
root = merge(new Node<AnyType>(x),root);
}
/**
* 删除最小元素
* @return
*/
public AnyType deleteMin(){
if(root == null)
return null; AnyType item = root.element;
root = merge(root.left,root.right); return item;
}
/**
* 将h1和h2两个堆合并，返回根节点(递归的方式实现)
* @param h1
* @param h2
* @return
*/
private Node<AnyType> merge(Node<AnyType> h1, Node<AnyType> h2) {
if(h1 == null)
return h2;
if(h2 == null)
return h1;
if(h1.element.compareTo(h2.element)<0){
//h1<h2
return merge1(h1,h2);
}else{
return merge1(h2,h1);
}
}
/**
* 将较小的堆min和较大的堆max合并，返回根节点
* @param min 较小的堆,不为null
* @param max 较大的堆，不为null
* @return
*/
private Node<AnyType> merge1(Node<AnyType> min, Node<AnyType> max) {
if(min.left==null) //min是一个叶子节点
min.left = max;
else{
min.right = merge(min.right,max); //较小堆的右子堆和较大堆合并
if(min.left.npl<min.right.npl){
swapChildren(min);
}
min.npl = min.right.npl+1;
}
return min;
}
/**
* 交换节点的左右子堆
* @param min
*/
private void swapChildren(Node<AnyType> min) {
Node temp = min.left;
min.left = min.right;
min.right = temp;
}
/**
* 非递归的方式来写一下
* @param min
* @param max
* @return
*/
/* private Node<AnyType> merge2(Node<AnyType> h1, Node<AnyType> h2) {
while(h1!=null && h2!=null){ }
}*/
public static void main(String[] args) {
LeftHeap<Integer> heap = new LeftHeap<>();
for(int i=0;i<10;i++)
heap.insert(i);
print(heap);
} public static void print(LeftHeap h){
while(h.root!=null){
System.out.println(h.deleteMin());
}
}
}