经典的二叉堆已经可以在$O(log N)$的复杂度的情况下维护堆这样的数据结构，也有d-堆可以维护成$O( log_d N)$（虽然pop操作的复杂度是$O(d log_d N)$），然而这两种堆不能满足$O(log N)$的合并操作，它们的经常是$O(N log N)$，即每次将一个堆中的堆顶拿出来放到另一个堆里。虽然有很多情况不经常合并，但有时候我们就是想要合并堆，还想频繁地合并，这时候二叉堆的性能就显得不是很好了。左偏树首先解决了合并问题。
左偏树像二叉堆一样是个二叉树，但是并不是完全二叉树。左偏树定义时用到了一个附加值：$npl$。$npl(X)$指节点$X$通向$NULL$的最短路径。若$X$只有一个子节点或者没有，那么$npl(X)=0$；否则，若规定$npl(NULL)=-1$，则$npl(X) = min { npl(left(X)) , npl(right(X)) } + 1$。乍一看像是高度的定义，只不过$max$换成了$min$。
左偏树的定义如下：对于左偏树$T$，要么没有子树或只有左子树，要么左右子树$L$、$R$满足：$mpl(L) geq npl(R)$，同时左右子树都是左偏树。
满足条件的左偏树有性质：
1、对于树根$T$，总有：$npl(T) = npl(right(T)) + 1$。
2、对于$T$，若$npl(T) = l$，则整棵树的节点数不少于$2^l -1$。
性质1很好得出；性质2书上利用数学归纳法。不过简单讲就是
$npl(left(T)) geq l-1$，对于每个具有左右子树的结点$X$，若$npl(X) = l_i$，取$npl(left(X)) = l_i-1$，同时由性质1得对应的右子树$npl(R) = l_i - 1$，可得左右子树全等（这里用到数学归纳法），那么这就是一棵满二叉树，$N = 2^l - 1$，由于左子树总是可以比这种情况还多任意多节点，所以这样就可以得到性质2。性质2反过来讲相当于若$T$有$N$个节点，那么$npl(T) leq log N$（相当于右路径的长度）（右路径为从根一直通向右子树直到$NULL$的路径）。左偏树满足这个性质后，总是把合并放到右路径上解决，这样保证了合并也是$O(log N)$的时间复杂度。
合并是这样的：合并两棵树时，令根的键值小树的根为新根，再递归合并新根的右子树和另一棵树。回溯时若发现某一结点不满足左偏树的定义，即左子树的$npl$小于右子树的$npl$，那么交换左右子树，这样合并操作总能保持$O(log N)$。这样做之后，插入即合并一个节点和原树，删除堆顶即合并树根的两个子树作为新根。
代码：
#include<cstdio> #define min(a,b) (a<b?a:b) #define nil 0 #define MXN 100000+1 int val[MXN],left[MXN],right[MXN],npl[MXN],recycle[MXN]; int root,ntop,rtop=-1; int newnode(int k){ int nw; if(rtop==-1) nw=++ntop; else nw=recycle[rtop--]; val[nw]=k; left[nw]=right[nw]=nil; npl[nw]=1; return nw; } void update(int now){ npl[now]=min(npl[left[now]],npl[right[now]])+1; return; } void swap(int &a,int &b){ int t=a; a=b,b=t; return; } int merge(int A,int B); int merge1(int A,int B); int merge(int A,int B){ if(A==nil) return B; if(B==nil) return A; if(val[A]<val[B]) return merge1(A,B); else return merge1(B,A); } int merge1(int A,int B){ if(left[A]==nil) left[A]=B; else{ right[A]=merge(right[A],B); if(npl[left[A]]<npl[right[A]]) swap(left[A],right[A]); npl[A]=npl[right[A]]+1; } return A; } void insert(int k){ int ins=newnode(k); if(root==nil) root=ins; else root=merge(root,ins); return; } int top(){ return val[root]; } void pop(){ recycle[++rtop]=root; int y=merge(left[root],right[root]); root=y; return; } int main(){ int p,x; while(1){ scanf("%d",&p); if(p==0) break; if(p==1) printf("%d ",top()); if(p==2){ scanf("%d",&x); insert(x); } if(p==3) pop(); } return 0; }
另外讲一下左偏树的变种：斜堆。斜堆只是把$npl$这个限制条件拿掉，每次合并不论情况，总是交换左右子树，这样使得期望的复杂度是$O(log N)$。像Splay一样，斜堆是自调整式数据结构，不需要记录任何额外变量。但是斜堆存在的劣势是右路径有时可能变得较长，面对较大数据递归时可能超过深度。不过左偏树和斜堆都可以写出非递归的程序，所以这不是太大的问题。
注：虽然在堆里实现查找多数情况下不现实，但是有时候堆还是被要求具有更改某些节点键值的不合理操作。如果想要具有减小键值这一操作（暂时不管如何找到应该减小键值的节点），那么左偏树或者斜堆都要记录父亲指针，进行向上调整。不过这无法保证对数时间复杂度。这是更强大的可并堆出现的原因之一。