《数据结构、算法与应用 —— C++语言描述》学习笔记 — 优先级队列 — 左高树
一、左高树1、外部节点2、高度优先左高树（1）定义（2）特性（3）HBLT 与 大小根树3、重量优先左高树4、最大HBLT的插入5、最大HBLT的删除6、两棵最大HBLT的合并7、HBLT的初始化二、左高树实现1、链式二叉树修改2、左高树接口3、左高树合并私有接口4、查找最大元素5、元素删除6、元素插入7、左高树合并8、初始化9、复杂性分析10、书中错误一、左高树
前面所学习的堆结构是一种隐式数据结构。用完全二叉树表示的堆在数组中式隐式存储的（即没有明确的指针或其他数据能够用来重塑这种结构）。由于没有存储结构信息，这种表示方法的空间利用率很高，它实际上没有浪费空间。而且它的时间效率也很高。尽管如此，它并不适合于所有优先级队列的应用，尤其是当两个优先级队列或多个长度不同的队列需要合并时，这时我们就需要其他数据结构了，比如左高树。
1、外部节点
考察一棵二叉树，它有一类特殊的节点叫做外部节点，它代替树中的空子树。其余节点叫做内部节点。增加了外部节点的二叉树被称为扩充二叉树。如图所示，灰色方框节点表示外部节点：
2、高度优先左高树
令s(x)表示从节点x到其子树的外部节点的所有路径中最短的一条。根据s(x)的定义，若x是外部节点，则s的值为0；若x为内部节点，则s的值为：min{s(L),s(R)}+1min\{s(L),s(R)\}+1min{s(L),s(R)}+1
其中，L与R分别为x的左右孩子。扩充二叉树中各节点的s值如图所示：
（1）定义
一棵二叉树被称为高度优先左高树（HBLT），当且仅当任何一个内部节点的左孩子的s值都大于或等于右孩子的s值。
上图所示的二叉树不是HBLT。考察外部节点a的父节点，它的左孩子的s值为0，而右孩子的值为1，尽管其他内部节点均满足HBLT的定义。若将节点a的父节点的左右子树交换，则该树成为HBLT。
（2）特性
令x为HBLT的一个内部节点，则：
① 以x为根的子树的节点数目至少为 2s(x)−12^{s(x)}-12s(x)−1
② 若以x为根的子树有m个节点，那么s(x)最多为 log2(m+1)\log_2{(m+1)}log2(m+1)
③ 从x到一外部节点的最右路径的长度为s(x)。
（3）HBLT 与 大小根树
若一棵 HBLT 同时还是大根树，则称为最大HBLT。若一棵 HBLT 同时还是小根树，则称为最小HBLT。
最大优先级队列可以用最大HBLT表示，最小优先级队列可以用最小HBLT表示。
3、重量优先左高树
如果我们考虑的不是路径长度，而是节点数目，那么我们可以得到另一种左高树。定义重量w(x)是以节点x为根的子树的内部节点数目。若x是外部节点，则它的重量为0；若x是内部节点，则它的重量是其孩子节点的重量之和加1。扩充二叉树中的各节点重量如图：
一棵二叉树被称为重量优先左高树（WBLT），当且仅当其任何一个内部节点的左孩子的w值都大于或等于右孩子的w值。若一棵若一棵 WBLT 同时还是大根树，则称为最大WBLT。若一棵 WBLT 同时还是小根树，则称为最小WBLT。
同 HBLT 类似，具有m个节点的 WBLT 的最右路径长度最多为 log2(m+1)\log_2{(m+1)}log2(m+1)。使用 WBLT 或 HBLT，可移植性优先级队列的查找、插入、删除操作，其时间复杂性与堆相同。和堆一样，WBLT 与 HBLT 可以在线性时间内完成初始化。用 WBLT 或 HBLT 表示的两个优先级队列可以在对数时间内合并为一个，而用堆表示的优先级队列做不到这一点。
下面我们以 HBLT 为例介绍相关操作的实现，WBLT 与之类似。
4、最大HBLT的插入
最大HBLT的插入操作可以利用最大HBLT的合并操作来实现。假定将元素x插入名为H的最大HBLT中。如果构建一棵仅有一个元素x的最大 HBLT ，然后将它与H进行合并，那么合并后的最大HBLT将包含H的全部元素和元素x。因此，要插入一个元素，可以先建立一棵新的只包含这个元素的HBLT，然后将这棵新的HBLT与原来的HBLT合并。
5、最大HBLT的删除
最大元素在根中。若根被删除，则分别以左右孩子为根的子树是两棵最大HBLT。将这两棵最大HBLT合并，便是删除后的结果。因此，删除操作可以通过删除根元素之后的两棵子树的合并来实现。
6、两棵最大HBLT的合并
具有n个元素的HBLT，其最右路径的长度为 O(logn)O(log n)O(logn)，一个算法要合并两棵HBLT，只能在遍历其最右路径中进行。由于在每个节点上实施合并所时间为O(1)O(1)O(1)，所以合并算法的时间复杂性是合并后节点数的对数。因此算法从两棵HBLT的根开始仅沿右孩子移动。
合并策略最好用递归来实现。令A、B为需要合并的两棵最大HBLT。若一个为空，则另一个便是合并的结果。假设两者均不为空。为实现合并，先比较两个根元素，较大者作为合并后的根。假定A的根较大，且左子树为L。令C是A的右子树与B合并而成的 HBLT。A与B合并的结果是以A为根，以L和C为子树的最大HBLT。如果L的s值小于C的s值，则C为左子树，否则L为左子树。
7、HBLT的初始化
初始化过程是将n个元素逐个插入最初为空的最大HBLT，所需时间为O(nlogn)O(nlog n)O(nlogn)。为得到具有线性时间的初始化算法，我们首先创建n个仅含一个元素的最大HBLT，这n棵树组成一份FIFO队列，然后从队列中依次成对删除HBLT，然后将其合并后再插入队列末尾，直到队列只有一棵HBLT为止。
二、左高树实现
我们这里通过继承前面实现的链式二叉树实现左高树，因为左高树并不需要存储额外的数据。
1、链式二叉树修改
链式二叉树的修改包括：
（1）私有成员变为受保护成员：
template<typename T>class linkedBinaryTree : public binaryTree<T>{protected:binaryTreeNode<T>* root = nullptr;int treeSize = 0;std::function<void(T)> visitFunc;std::function<void(binaryTreeNode<T>*)> visitNodeFunc;...}
（2）将析构时的操作提取为clear函数：
template<typename T>inline void linkedBinaryTree<T>::clear(){visitNodeFunc = [](binaryTreeNode<T>* node) {delete node; };postOrder(root);visitNodeFunc = std::function<void(binaryTreeNode<T>*)>();}
2、左高树接口
左高树的节点类型是std::pair<int, T>，first成员表示节点的s值，second成员表示元素本身。
#pragma once#include <utility>#include <stdexcept>#include <queue>#include <algorithm>#include <functional>#include <iostream>#include "priorityQueue.h"#include "../binaryTree/binaryTreeNode.h"#include "../binaryTree/linkedBinaryTree.h"template <typename T, typename Predicate = std::greater_equal<T>>class hblt : public priorityQueue<T>, linkedBinaryTree<std::pair<int, T>>{public:using NodeType = binaryTreeNode<std::pair<int, T>>;virtual bool empty() const override;virtual int size() const override;virtual T& top() override;virtual void pop() override;virtual void push(const T& element) override;void meld(const hblt& other);void meld(hblt&& other);void initialize(T* origin, int arrayLength);void output();private:void meld(NodeType* &left, NodeType* &right);void checkSize();int& nodePathLen(NodeType* node);T& nodeData(NodeType* node);};
3、左高树合并私有接口
所有的左高树修改操作都涉及到左高树合并的功能。前面的算法已经描述了此函数的大部分，最后我们需要对合并后树根的节点长度进行更新。其实现如下：
template<typename T, typename Predicate>inline void hblt<T, Predicate>::meld(NodeType* &left, NodeType* &right){using std::swap;if (left == nullptr){left = right;return;}if (right == nullptr){return;}Predicate pred;if (!pred(nodeData(left), nodeData(right))){swap(left, right);}meld(left->rightChild, right);if (left->leftChild == nullptr || (left->rightChild != nullptr && nodePathLen(left->leftChild) < nodePathLen(left->rightChild))){swap(left->leftChild, left->rightChild);}if (left->leftChild != nullptr){nodePathLen(left) = nodePathLen(left->leftChild) + 1;}else{nodePathLen(left) = 1;}}template<typename T, typename Predicate>inline int& hblt<T, Predicate>::nodePathLen(NodeType* node){return node->element.first;}template<typename T, typename Predicate>inline T& hblt<T, Predicate>::nodeData(NodeType* node){return node->element.second;}
4、查找最大元素
template<typename T, typename Predicate>inline T& hblt<T, Predicate>::top(){checkSize();return nodeData(this->root);}template<typename T, typename Predicate>inline void hblt<T, Predicate>::checkSize(){if (this->treeSize == 0){throw std::overflow_error("no element in the tree");}}
5、元素删除
template<typename T, typename Predicate>inline void hblt<T, Predicate>::pop(){checkSize();auto rightChild = this->root->rightChild;auto leftChild = this->root->leftChild;delete this->root;this->root = this->root->leftChild;meld(this->root, rightChild);--this->treeSize;}
6、元素插入
template<typename T, typename Predicate>inline void hblt<T, Predicate>::push(const T& element){auto tempRoot = new NodeType(std::make_pair(1, element));meld(this->root, tempRoot);++this->treeSize;}
7、左高树合并
这里我们提供了两个接口分别用于可移动的树和不可移动的树。树中的实现移动了一个non-const引用的树，这并不是一个好的选择。使用右值引用暗示用户我们将会直接使用被移动树的数据。
template<typename T, typename Predicate>inline void hblt<T, Predicate>::meld(const hblt& other){auto tempTree = new hblt(other);meld(std::move(*tempTree));delete tempTree;}template<typename T, typename Predicate>inline void hblt<T, Predicate>::meld(hblt&& other){meld(this->root, other.root);this->treeSize += other.treeSize;other.root = nullptr;}
8、初始化
template<typename T, typename Predicate>inline void hblt<T, Predicate>::initialize(T* origin, int arrayLength){std::queue<NodeType*> meldNodes;std::for_each(origin, origin + arrayLength, [&meldNodes](T element) {meldNodes.push(new NodeType(std::make_pair(1, element))); });while (meldNodes.size() > 1){auto left = meldNodes.front();meldNodes.pop();auto right = meldNodes.front();meldNodes.pop();meld(left, right);meldNodes.push(left);}if (!meldNodes.empty()){this->clear();this->treeSize = arrayLength;this->root = meldNodes.front();meldNodes.pop();}}
9、复杂性分析
查找功能的时间复杂度是O(1)O(1)O(1)。插入、删除和合并的时间复杂度与私有方法meld相同，本质上都是两棵二叉树的合并。私有方法meld仅沿着left和right的右子树移动，因此该函数的复杂性为O(s(left)+s(right))=O(logm+logn)=O(logn)O(s(left)+s(right))=O(log m + log n)=O(log n)O(s(left)+s(right))=O(logm+logn)=O(logn)。
在分析初始化函数的复杂性时，为了简单起见，假设n是2的幂次方。首先合并n2\frac{n}{2}2n对HBLT，每棵树中含有1个元素；然后合并n4\frac{n}{4}4n对HBLT，每棵树中含有2个元素；如此下去。如果每棵含有2i2^i2i个元素，那么合并两棵最大HBLT耗时O(i+1)O(i+1)O(i+1)。因此initialize函数所花费的总时间为：O(n2+2∗n4+⋅⋅⋅)=O(n∑i2i)=O(n)O(\frac{n}{2}+2*\frac{n}{4}+···)=O(n\sum\frac{i}{2^i})=O(n)O(2n+2∗4n+⋅⋅⋅)=O(n∑2ii)=O(n)。
10、书中错误
这个类书中给出了测试代码却没有给出输出结果。如果我们尝试编译作者提供的代码会发现和我们自己的编译结果是绝对对不上的。原因在于书中合并函数的实现是有问题的。问题出在第68行：
if (x->leftChild == NULL){x->leftChild = x->rightChild;x->rightChild = NULL;// 原实现// x->element.first = 1;// 修改后if (x->leftChild == NULL){x->element.first = 1;}else{x->element.first = x->leftChild->element.first + 1;}}
如果左子树为空，将右子树赋值给左子树后，最短路径的判断应该取决于新的左子树是否为空，而不是写死为1.
