左偏树

左偏树 Leftist Tree // min leftist tree // T must define < // M: the size of the heap template<typename T,size_t M,typename Cmp=less<T>> struct Leftist { static Cmp cmp; T val[M]; int l[M],r[M],d[M]; int nn; // number of node void init() { nn=0; } // using val to build a leftist tree // return the id of the root int build(int n,T val_[]) { queue<int> qu; for(int i=1;i<=n;i++) qu.push(i); int u,v; while(qu.size()>1) { u=qu.front(); qu.pop(); v=qu.front(); qu.pop(); merge(u,v); qu.push(u); } return qu.front(); } int newtree(T v) { val[++nn]=v; r[nn]=l[nn]=d[nn]=0; return nn; } void merge(int &x,int y) // merge …