左偏树真是个超好写的东西！支持合并，插入，删除最小值三个操作。后两个操作都可以看成第一个操作的拓展，如删除最小值是合并根的两棵子树，插入则直接将元素看作一个左偏树——所以只要写个Merge就可以了！

左偏树保证左子树深度大于等于右子树深度，同时符合堆性质。合并LT1,LT2（假设LT1中最小值比LT2小，否则交换）时，递归合并LT1的右子树和LT2替换掉LT1，然后如果LT1不符合左偏性质，则交换LT1的子树。

小小的提示：构树时，逐个插入是O(nlgn)的。这里可以有O(n)的复杂度的算法：先把所有元素构成n个单元素左偏树放进队列，然后每次取出两个合并后放入队列尾，直到只剩下一棵左偏树。

#include <stdio.h>
#include <string.h>
#define maxn 100000
#define Type int
#define cmp(x,y) ((x)<(y))
typedef struct _LT{struct _LT *c[2];Type v;int d;}LT,*PLT;
LT st[maxn],*stp=st;
PLT Merge(PLT LT1,PLT LT2){
	PLT t;
	if(!LT1)return LT2;if(!LT2)return LT1;
	if(cmp(LT2->v,LT1->v))t=LT1,LT1=LT2,LT2=t;
	LT1->c[1]=Merge(LT1->c[1],LT2);
	if(!LT1->c[0]||LT1->c[0]->d<LT1->c[1]->d)t=LT1->c[0],LT1->c[0]=LT1->c[1],LT1->c[1]=t;
	return (LT1->d=LT1->c[0]?LT1->c[0]->d+1:0),LT1;
}inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}main(){
	return 0;
}

• inline
• block