由于常用的二叉堆对于合并不同的优先队列较为麻烦，于是左偏树出现了！
左偏树在普通的优先队列的基础上，满足特定条件，从而更加快速的去合并不同的优先队列。
首先要引入一个概念：
零路径（npl）:
节点距离包含null 子节点的节点（外节点）的最短长度，对于空节点零路径为-1，包含空子结点的节点零路径为0。
对于一颗左偏树：
1、堆序
2、节点左子节点的零路径长>=右节点的零路径长（左偏）
3、（推论）节点的零路径npl=右子节点的零路径长+1
对于左偏树我们关心的主要是以下三个操作：
合并（merage）、删除（remove）、插入（insert）
但其实偷懒下来只需要关心一个操作——合并
现在我们来看看如何实现：
class LeftistNode{ public: int w,npl; LeftistNode* lch,*rch; explicit LeftistNode(int key,int _npl=0,LeftistNode* _l= nullptr,LeftistNode* _r= nullptr) :w(key),npl(_npl),lch(_l),rch(_r){}; }; class LeftistHeap{ private: LeftistNode* root; public: LeftistHeap():root(nullptr){}; ~LeftistHeap(){ destroy(root); }; void destroy(LeftistNode*& r){ if(r){ LeftistNode* x=r->lch,*y=r->rch; delete r; r=nullptr; destroy(x); destroy(y); } } static inline void swap(LeftistNode*& x,LeftistNode*& y){ LeftistNode* tmp=x; x=y; y=tmp; } LeftistNode* merage(LeftistNode*& x,LeftistNode*& y){ if(x==nullptr)return y; if(y==nullptr)return x; if(x->w>y->w)//root<=_o swap(x,y); x->rch=merage(x->rch,y); if(x->lch==nullptr||x->lch->npl<x->rch->npl){ swap(x->lch,x->rch); } if(x->lch==nullptr||x->rch== nullptr)x->npl=0; else{ x->npl=(x->lch->npl<x->rch->npl)?x->lch->npl+1:x->rch->npl+1; } return x; } void merage(LeftistHeap& _o){ root=merage(root,_o.root); _o.root=nullptr; } void insert(int key){ auto tmp=new LeftistNode(key); root=merage(root,tmp); } int remove(){ int charming=root->w; LeftistNode* x=root->lch; LeftistNode* y=root->rch; delete root; root=merage(x,y); return charming; } bool empty(){return !root;} };
对于remove操作：其实就是俩个子节点的合并操作
对于insert操作：其实就是一颗只有一个节点的树和另一个树的合并操作
合并操作的基本过程：
1、若有空节点，返回非空节点的指针
2、判断树x的权是否小于树y的权，如果不是就交换俩颗树（只是为了更方便操作）
3、让树x的右子节点和树y进行合并，树x作为新树的根节点
4、从底层递归向上时，要检查左子树npl是否>=右子树npl,否则交换
5、更新根节点npl
6、返回根节点
好耶，可以睡觉了
原文：https://www.cnblogs.com/CicacdaTwelve/p/14676394.html