本文代码下载：
方式1：公众号【多栖技术控小董】回复【3586】免费获取下载链接方式2：CSDN下载链接：/download/qq_41453285/12046050方式3：Github下载链接（进入之后下载里面的maxHblt.zip文件）：/dongyusheng/Interview-algorithm/tree/master/c%2B%2BAlgorithms前面文章介绍了用堆实现优先级队列：/qq_41453285/article/details/103639243用堆实现优先级队列的空间利用率很高，而且效率也很高，但是并不适用于所有优先级队列，尤其当两个优先级队列或多个长度不同的队列需要合并的时候，这时就需要其他的数据结构了，左高树就能满足这种需要堆与左高树的异同：WBLT、HBLT可以执行优先级队列的查找、插入、删除操作，时间复杂度与堆相同WBLT、HBLT和堆一样，可以在线性时间内完成初始化用WBLT、HBLT表示的两个优先级队列可以在对数时间内合并为一个，而桶堆表示的优先级队列却不行
一、扩充二叉树
如果一棵二叉树，有一类特殊的节点叫做外部节点，它替代树中的空子树。其余节点叫做内部节点增加了外部节点的二叉树称为扩充二叉树例如下图a是一棵二叉树，下图b是图a的扩充二叉树（外部节点用[a-f]表示）高度s的定义
令s(x)是节点x到其子树的外部节点的所有路径中最短的一条，则有： 若x是外部节点，则s(x)=0若x是内部节点，则s(x)=min{s(L),s(R)+1}，其中L、R分别代码左、右孩子例如，下面的扩充二叉树（图b），每个节点的s值如图c所示
重量w的定义
如果不以路径长度s来对左高树进行定义，而是以节点数目来定义，那么就可以得到另一种左高树节点的重量（w）：若x是外部节点，则w(x)=0若x是内部节点，则w(x)=w(子节点的重量)+1例如，下面的扩充二叉树，每个节点的w值如下图所示
二、高度优先左高树(HBLT)
定义：当且仅当其任何一个内部节点的左孩子的s值都大于或等于右孩子的s值，称为高度优先左高树(height-biased leftist tree，HBLT)例如下图就是一个高度优先左高树(HBLT)，其中阴影部分代表外部节点定理
令x为HBLT的一个内部节点，则有： 1).以x为根的子树的节点数目至少为2).若以x为根的子树有m个节点，那么s(x)最多为3).从x到一外部节点的最右路径（即从x开始沿右孩子移动的路径）的长度为s(x)
最大HBLT、最小HBLT
若一棵HBLT同是还是大根树，那么称之为最大HBLT（max HBLT），可用于实现最大优先级队列若一棵HBLT同是还是小根树，那么称之为最小HBLT（min HBLT），可用于实现最小优先级队列例如下图3个都是最大HBLT例如下图3个都是最小HBLT
最大HBLT的插入
最大HBLT的插入操作可利用最大HBLT的合并操作来实现插入的策略：1.假设元素x要插入名为H的最大HBLT中2.先建立一棵新的只包含x元素的HBLT3.然后将这棵新的HBLT与名为H的HBLT进行合并4.合并之后的HBLT就为插入之后最终的HBLT
最大HBLT的删除
最大HBLT与大根堆一样，最大元素在根中。因此删除操作也是删除根节点删除操作也是利用最大HBLT的合并操作来实现删除的策略：1.若根被删除，则分别以根节点的左右孩子节点为根的子树是两棵最大HBLT2.然后将这棵最大HBLT合并，之后便是删除后的结果
两棵HBLT的合并
具有n个元素的HBLT，其最右路径的长度为O()。一个算法要合并两棵HBLT，只能在遍历其最右路径中进行。由于在每个节点上实施合并所需时间为O(1)，所以合并算法的时间复杂性是合并后节点数的对数。因此算法从两棵HBLT的根开始仅沿右孩子移动合并的策略：1.假设A、B是两棵需要合并的最大HBLT。如果一者为空，则另一个便是合并的结果；如果两者均不为空，则进行以下步骤2.先比较两个HBLT的根，较大者的根作为合并后的HBLT的根3.假设A的根大于B，且A的左子树为L4.然后将A的右子树与B合并，然后形成一棵名为C的HBLT（如果A没有右子树，那B就什么都不做）5.然后将C与A合并6.如果L的s值小于C的s值，则以C为左子树，L为右子树；否则，L为左子树，C为右子树合并的策略需要使用递归来实现（因为通过上面的步骤我们知道，如果将A的右子树与B进行合并，也是一次HBLT合并的操作，因此是递归的特性）下面的演示案例中：每个节点的s值标在节点的外部，元素的值标在节点的里面。并且根较大的树我们放置在左边，右边的HBLT用阴影表示演示案例1：1.假设a)是两棵想要合并的HBLT2.因为9的右子树为空，所以就不存在9的右子树与7进行合并的操作3.然后将7与9为根的HBLT进行合并（图b)所示）4.合并之后9的左子树的s值为0（也就是外部节点的s值），而右子树（7）的s值为1，因此将7作为9的左子树。最终合并的结果如c)所示演示案例2：1.假设d)是两棵想要合并的HBLT2.因为10的右子树为空，所以就不存在10的右子树与7进行合并的操作3.然后将7与9为根的HBLT合并（如图e)所示）4.合并之后检查10的左子树的s值与右子树的s值相等，因此就不交换。最终的结果如图e)所示演示案例3：1.假设f)是两棵想要合并的HBLT2.18的右子树不为空，因此需要将18的右子树与10为根的HBLT进行合并，合并之后的结果如上图e)所示3.18的右子树与10为根的HBLT合并之后产生一个新的HBLT，然后将这个HBLT作为18的右子树（如图g)所示）4.合并之后，然后开始比较18的左右子树的s值，比较之后，发现18的右子树的s值比左子树的s值大，因此需要将左右子树进行互换。互换之后的结果如h)所示，这也是最终的合并结果演示案例4：1.假设i)是两棵想要合并的HBLT2.因为40的右子树不为空，因此将40的右子树与以18为根的HBLT进行合并，合并的结果就是我们上面所介绍的h)所示3.合并之后将h)作为20的右子树（如图j)所示）4.合并之后，然后开始比较40的左右子树的s值，比较之后，发现40的右子树的s值比左子树的s值大，因此需要将左右子树进行互换。互换之后的结果如k)所示，这也是最终的合并结果
最大HBLT的初始化
初始化过程是将n个元素逐个插入最初为空的最大HBLT，所需时间为O()。并且也用到了合并操作初始化的策略：1.首先创建n个仅包含一个元素的最大HBLT，将这n棵树组成一个FIFO队列2.然后从队列中依次成对删除HBLT，然后将其合并后再插入队列末尾，直到队列只有一棵HBLT位置演示案例：1.假设我们希望构造一棵最大HBLT，其具有5个元素：7、1、9、11、22.先将这5个元素做个分别作为5棵单独的HBLT，然后组成一个FIFO队列3.接着从队列中取出一对HBLT进行合并（上面可以看出是7和1这两个HBLT），将7和1进行合并（如图a)所示）4.然后将7和1组成的HBLT放入到队列的尾部5.接着从队列头部再次取出两棵HBLT，此时为9和11，然后将9和11组成一棵HBLT（如图b)所示）6.然后将9和11组成的HBLT放入到队列的尾部（注意，此时队列中只有3棵HBLT了）7.然后从队列中再取出两棵HBLT进行合并，此时取出的是1和7、2组成的HBLT，然后将两者合并（如图c所示）8.然后将合并后的结果放入到队列尾部（注意，此时队列中只有2棵HBLT了）9.最后队列中只有两棵HBLT了（就是c)和b)），然后将b)和c)进行合并，最终的结果如d)所示
二、重量优先左高树(WBLT)
定义：当且仅当其任何一个内部节点的左孩子的w值都大于或等于其右孩子的w值，称为重量优先左高树(wieght-biased leftist tree，WBLT)最大HBLT、最小HBLT：若一棵WBLT同是还是大根树，那么称之为最大WBLT（max WBLT），可用于实现最大优先级队列若一棵WBLT同是还是小根树，那么称之为最小WBLT（min WBLT），可用于实现最小优先级队列与HBLT异同：同HBLT类似，具有m个节点的WBLT的最右路径长度最多为WBLT的查找、插入、删除、合并、初始化和HBLT的类似，所以可以参考上面HBLT的操作三、编码实现（最大HBLT）
头文件定义
#include <iostream>#include <string>#include <queue>using std::cout;using std::endl;using std::cin;using std::string;using std::pair;using std::queue;异常类定义
class illegalParameterValue{string message;public:illegalParameterValue(const char *theMessage = "Illegal Parameter Value") :message(theMessage) {}const char *what() {return message.c_str();}};class queueEmpty{public:queueEmpty(string theMessage = "Invalid operation on empty queue"){message = theMessage;}const char *what() {return message.c_str();}private:string message;};
树节点定义
用来表示树中的每一个节点
template<typename T>struct binaryTreeNode{T element;struct binaryTreeNode<T>* leftChild, *rightChild;binaryTreeNode() { this->leftChild = this->rightChild = nullptr; }binaryTreeNode(const T& theElement) :element(theElement) {this->leftChild = this->rightChild = nullptr;}binaryTreeNode(const T& theElement,const struct binaryTreeNode<T>* theLeftChild,const struct binaryTreeNode<T>* theRightChild) :element(theElement) {this->leftChild = theLeftChild;this->rightChild = theRightChild;}};抽象类定义
template<typename T>class maxPriorityQueue{public:virtual ~maxPriorityQueue() {}virtual bool empty()const = 0;//当队列为空返回true;否则返回falsevirtual int size()const = 0;//返回队列的元素个数virtual const T& top() = 0;//返回优先级最大的元素的引用virtual void pop() = 0; //删除队首元素virtual void push(const T& theElement) = 0;//插入元素theElement};
主类定义
主类继承于maxPriorityQueue抽象类其中每个树节点类型为std::pait<int,T>类型 int：代表每个节点的s值T：代表每个节点的数值
template<typename T>class maxHblt :public maxPriorityQueue<T>{public:maxHblt() { this->root = nullptr; this->treeSize = 0;}~maxHblt() { erase(); }bool empty()const override {//当队列为空返回true;否则返回falsereturn this->treeSize == 0;}int size()const override { //返回队列的元素个数return this->treeSize;}const T& top()override {//返回优先级最大的元素的引用if (this->treeSize == 0)throw queueEmpty();return this->root->element.second;}void pop()override;//删除队首元素void push(const T& theElement)override;//插入元素theElementvoid initialize(T* theElement, int theSize);//初始化一个HBLTvoid erase(); //清空树void meld(maxHblt<T>& theHblt); //将本棵HBLT与参数所指的HBLT进行合并，内部调用私有方法meldvoid preOrderOutput()const { preOrder(this->root); }void inOrderOutput()const { inOrder(this->root); }void postOrderOutput()const { postOrder(this->root); }private:void preOrder(binaryTreeNode<std::pair<int, T>>* x)const;void inOrder(binaryTreeNode<std::pair<int, T>>* x)const;void postOrder(binaryTreeNode<std::pair<int, T>>* x)const;void clearTree(binaryTreeNode<std::pair<int, T>>* t);void meld(binaryTreeNode<std::pair<int,T>>* &x, binaryTreeNode<std::pair<int,T>>*& y);private:binaryTreeNode<std::pair<int,T>>* root; //根节点int treeSize; //树的大小};meld函数
根据上面介绍的HBLT合并原理，定义了此函数，用来合并两棵HBLT树
//将x和y两棵HBLT合并template<typename T>void maxHblt<T>::meld(binaryTreeNode<std::pair<int, T>>* &x, binaryTreeNode<std::pair<int, T>>*& y){//如果y为空，不进行合并if (y == nullptr)return;//如果x为空，那么就将y赋值给xif (x == nullptr){x = y;return;}//如果x的值小于y的值，进行交换if (x->element.second < y->element.second)std::swap(x, y);//将x的右子节点与y合并。如果x没有右子节点，那么就将y设置为x的右子节点meld(x->rightChild, y);//如果x的左子节点为空，将右子节点设置为左子节点if (x->leftChild == nullptr) {x->leftChild = x->rightChild;x->rightChild = nullptr;//因为把右子节点赋值给左子节点了，所以右子节点为空了，那么本节点的s值就为1了x->element.first = 1;}else //如果左子节点不为空，比较是否需要交换{//如果左子节点的s值比右子节点的小，那么就进行交换if (x->leftChild->element.first < x->rightChild->element.first) {std::swap(x->leftChild, x->rightChild);}//因为右子节点到外部节点之间的s值是最小的，所以就将x的s值设置为右子节点的s值+1x->element.first = x->rightChild->element.first + 1;}}pop、push函数定义
根据上面最大HBLT的删除、原理定义了下面的函数，都调用了meld合并函数
template<typename T>void maxHblt<T>::pop(){//如果HBLT为空，不能出队列if (this->treeSize == 0)throw queueEmpty();//得到根节点的左右子节点binaryTreeNode<std::pair<int, T>>* left = this->root->leftChild,*right=this->root->rightChild;//删除根节点，将左子节点变为新根节点，然后进行合并delete this->root;this->root = left;meld(this->root, right);this->treeSize--;}template<typename T>void maxHblt<T>::push(const T& theElement){//创建一个新节点binaryTreeNode<std::pair<int, T>> *q = new binaryTreeNode<std::pair<int, T>>(std::pair<int,T>(1, theElement));//将新节点与本HBLT进行合并this->meld(this->root,q);this->treeSize++;}erase、clearTree函数
erase用来清空整个HBLT树，调用了clearTree函数
template<typename T>void maxHblt<T>::erase(){//调用clearTreeclearTree(this->root);this->root = nullptr;this->treeSize = 0;}template<typename T>void maxHblt<T>::clearTree(binaryTreeNode<std::pair<int, T>>* t){//后序遍历删除if (t){clearTree(t->leftChild);clearTree(t->rightChild);delete t;}}initialize函数
根据上面介绍的FIFO初始化HBLT原则，定义了此函数
template<typename T>void maxHblt<T>::initialize(T* theElement, int theSize){//创建一个队列，用来初始化HBLTstd::queue<binaryTreeNode<std::pair<int, T>>*> q;//清空当前HBLTerase();//先建立一组HBLT，每个HBLT中只有一个节点for (int i = 1; i <=theSize; ++i)q.push(new binaryTreeNode<std::pair<int, T>>(std::pair<int, T>(1, theElement[i])));//theSize个HBLT，需要合并theSize-1次for (int i = 1; i <= theSize - 1; ++i){//从队列中取出两个HBLT进行合并binaryTreeNode<std::pair<int, T>>* b = q.front();q.pop();binaryTreeNode<std::pair<int, T>>* c = q.front();q.pop();//合并meld(b, c);//合并之后再次放入到队列中q.push(b);}if (theSize > 0)this->root = q.front();this->treeSize = theSize;}打印函数
分别为前序遍历、中序遍历、后序遍历
template<typename T>void maxHblt<T>::preOrder(binaryTreeNode<std::pair<int, T>>* x)const{if (x){std::cout << x->element.second<<" ";preOrder(x->leftChild);preOrder(x->rightChild);}}template<typename T>void maxHblt<T>::inOrder(binaryTreeNode<std::pair<int, T>>* x)const{if (x){inOrder(x->leftChild);std::cout << x->element.second << " ";inOrder(x->rightChild);}}template<typename T>void maxHblt<T>::postOrder(binaryTreeNode<std::pair<int, T>>* x)const{if (x){postOrder(x->leftChild);postOrder(x->rightChild);std::cout << x->element.second << " ";}}复杂度分析
演示案例1
int main(){maxHblt<int>* myMaxHblt = new maxHblt<int>();myMaxHblt->push(7);myMaxHblt->push(5);myMaxHblt->push(10);myMaxHblt->push(3);myMaxHblt->preOrderOutput();std::cout << std::endl;myMaxHblt->inOrderOutput();std::cout << std::endl;myMaxHblt->postOrderOutput();std::cout << std::endl;std::cout << std::endl;myMaxHblt->pop();myMaxHblt->preOrderOutput();std::cout << std::endl;myMaxHblt->inOrderOutput();std::cout << std::endl;myMaxHblt->postOrderOutput();std::cout << std::endl;std::cout << std::endl;return 0;}演示结果如下图所示：根据插入原则，其步骤如下当pop一个元素之后（删除根节点10），其步骤如下
演示案例2
int main(){maxHblt<int>* myMaxHblt = new maxHblt<int>();int arr[5] = { 0,7,5,10,3 };myMaxHblt->initialize(arr,4);myMaxHblt->preOrderOutput();std::cout << std::endl;myMaxHblt->inOrderOutput();std::cout << std::endl;myMaxHblt->postOrderOutput();std::cout << std::endl;std::cout << std::endl;myMaxHblt->pop();myMaxHblt->preOrderOutput();std::cout << std::endl;myMaxHblt->inOrderOutput();std::cout << std::endl;myMaxHblt->postOrderOutput();std::cout << std::endl;std::cout << std::endl;return 0;}这个演示案例调用了intialize函数，元素与演示案例1都是一样的，结果应该与演示案例1一样（备注：但是不知道为什么，结果与演示案例1不一样，待更新）
C++(数据结构与算法):42---优先级队列的实现（扩充二叉树 高度优先左高树(HBLT) 重量优先左高树(WBLT)）
