[ skew heap ] implementation 斜堆 實作

斜堆(Skew heap)也叫自適應堆(self-adjusting heap)，它是(重量)左偏樹的一個變種。
相較於(重量)左偏樹，斜堆不需記錄其高度或是節點個數(size)等附加域，其合併(merge)的方式也較為簡潔，效率也較高。和(重量)左偏樹一樣，斜堆的push、pop的時間複雜度為$\ord{log \; n}$、查詢最值為$\ord 1$。
關於複雜度分析
以下提供斜堆的實作，使用方法與STL priority_queue相似

	#include<functional>
	#ifndef SKEW_HEAP
	#define SKEW_HEAP
	template<typename T,typename _Compare=std::less<T> >
	class skew_heap{
	private:
	struct node{
	T data;
	node *l,*r;
	node(const T&d):data(d),l(0),r(0){}
	}*root;
	int _size;
	_Compare cmp;
	node *merge(node *a,node *b){
	if(!a||!b)return a?a:b;
	if(cmp(a->data,b->data))return merge(b,a);
	node *t=a->r;
	a->r=a->l;
	a->l=merge(b,t);
	return a;
	}
	void _clear(node *&o){
	if(o)_clear(o->l),_clear(o->r),delete o;
	}
	public:
	skew_heap():root(0),_size(0){}
	~skew_heap(){_clear(root);}
	inline void clear(){
	_clear(root);root=0;_size=0;
	}
	inline void join(skew_heap &o){
	root=merge(root,o.root);
	o.root=0;
	_size+=o._size;
	o._size=0;
	}
	inline void swap(skew_heap &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 skew heap.cpp hosted with ❤ by GitHub