重量左偏樹 weight-biased leftist tree

之前提到的左偏樹是深度左偏樹，雖然複雜度也是logn，但是重量左偏樹的速度在實作上是明顯較深度左偏樹快的
若是想了解深度左偏樹 height-biased leftist tree 或是左偏樹的理論請參考這篇文章
以下提供模板(使用方法與深度左偏樹相同):

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

view raw weight_biased_leftist_tree.cpp hosted with ❤ by GitHub