左偏樹 leftist tree

一個左偏樹同時滿足了heap及左偏的性質
設:
deep(x)為x到任意一個外部節點的最長路徑長度
滿足: deep(x)={0，x為外部節點 : 1+max(deep(x->leftchild),deep(x->rightchild))}
由於左偏堆已經不是完全二元樹，因此不能用數組存儲表示，需要用連結結構。
插入刪除最差複雜度$\ord{log \; n}$最佳$\ord 1$
插入時盡量往右邊插入，若不符合左偏性質則交換左右子樹
刪除則是將根節點的左右子樹合併，再直接刪除根節點
以下是模板:

	#include<functional>
	#ifndef LEFTIST_TREE
	#define LEFTIST_TREE
	template<typename T,typename _Compare=std::less<T> >
	class leftist_tree{
	private:
	struct node{
	T data;
	int deep;
	node *l,*r;
	node(const T&d):data(d),deep(1),l(0),r(0){}
	}*root;
	int _size;
	_Compare cmp;
	inline int deep(node *o){return o?o->deep:0;}
	node *merge(node *a,node *b){
	if(!a||!b)return a?a:b;
	if(cmp(a->data,b->data)){
	node *t=a;a=b;b=t;
	}
	a->r=merge(a->r,b);
	if(deep(a->l)<deep(a->r)){
	node *t=a->l;a->l=a->r;a->r=t;
	}
	a->deep=deep(a->l)+1;
	return a;
	}
	void _clear(node *&o){
	if(o)_clear(o->l),_clear(o->r),delete o;
	}
	public:
	leftist_tree():root(0),_size(0){}
	~leftist_tree(){_clear(root);}
	inline void clear(){
	_clear(root);root=0;_size=0;
	}
	inline void join(leftist_tree &o){
	root=merge(root,o.root);
	o.root=0;
	_size+=o._size;
	o._size=0;
	}
	inline void swap(leftist_tree &o){
	node *t=root;
	root=o.root;
	o.root=t;
	int st=_size;
	_size=o._size;
	o._size=st;
	}
	inline void push(const T&data){
	_size++;
	root=merge(root,new node(data));
	}
	inline void pop(){
	if(_size)_size--;
	node *tmd=merge(root->l,root->r);
	delete root;
	root=tmd;
	}
	inline const T& top(){return root->data;}
	inline int size(){return _size;}
	inline bool empty(){return !_size;}
	};
	#endif

view raw leftist_tree.cpp hosted with ❤ by GitHub

(感謝"脹脹的承翰"幫忙指正)
定義一個int為key的左偏樹:

//標準是大根堆
leftist_tree<int  > t;

//小根堆的左偏樹
leftist_tree<int ,greater<int > >t;

基本上與priority_queue的用法差不多，只是多了clear()及join()指令
t.clear();//將t清空
t.join(b);//將b加入t，並將b清空