优先队列2-左高树

继续是《数据结构算法与应用：C++语言描述》的笔记，这是第九章优先队列的内容。本节将介绍另一种实现优先队列的数据结构—左高树

高度与宽度优先的最大及最小左高树

上一节讲述的堆结构是一种隐式数据结构，用完全二叉树表示的堆在数组中时隐式存储的（即没有明确的指针或其他数据能够重构这种结构）。由于没有存储结构信息，这种描述方法空间利用率很高，事实上是没有空间浪费，尽管堆结构的时间和空间效率都很高，但它不适合所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时，需要借助其他数据结构来实现这类应用，比如左高树(leftist tree)。

考察一棵二叉树，如下图9-6a所示，它有一类特殊的节点叫做外部节点，用来代替树中的空子树，其余节点叫做内部节点。增加了外部节点的二叉树被称为扩充二叉树，如下图9-6b所示，外部节点用阴影框表示，并且为了方便起见，这些节点用a~f标注。

令$s(x)$是从节点$x$到它的子树的外部节点的所有路径横纵最短的一条，根据其定义可知，如果$x$是外部节点，则$s$=0，若$x$是内部节点，则其$s$值为$min{s(L),s(R)}+1$，其中$L,R$分别是$x$的左右子树。所以上述扩充二叉树各节点的s值如上图9-c所示。

定义 [高度优先左高树] 当且仅当一棵二叉树的任何一个内部节点，其左孩子的$s$值大于等于右孩子的$s$值时，该二叉树是高度优先左高树(height-biased leftist tree,HBLT)。

定义 [最大(小)HBLT] 即同时是最大(小)树的HBLT;

图9-6a所示的二叉树并不是HBLT，因为外部节点a的父节点，其左孩子$s$=0，右孩子$s$=1，不满足条件，如果将这两个子树进行交换就可以满足HBLT的条件。

定理9-1 若x是一个HBLT的内部节点，则
1) 以$x$为根的子树的节点数目至少是$2^{s(x)}-1$.
2) 若子树$x$有$m$个节点，$s(x)$最多为$log_2(m+1)$
3) 通过最右路径（即路径是从$x$开始沿右孩子移动）从$x$到达外部节点的路径长度是$s(x)$。

可以通过考察子树的节点数目来得到另一类左高树。定义$x$的重量$w(x)$是以$x$为根的子树的内部节点数目。如果$x$是外部节点，则其重量为0；若$x$是内部节点，则其重量是其孩子节点的重量之和加1，如上图9-6d展示了二叉树各节点的重量。

定义 [重量优先左高树] 当且仅当一棵二叉树的任何一个内部节点，其左孩子的$w$值大于等于右孩子的$w$时，该二叉树为重量优先左高树(weight-biased leftist tree,WBLT);

[最大(小)WBLT]即同时又是最大(小)树的WBLT。

同HBLT类似，具有$m$个节点的WBLT的最右路径长度最多为$log_2(m+1)$。可以对WBLT和HBLT执行优先队列的查找、插入和删除操作，其时间复杂性与堆的相应操作相同。并且跟堆一样，WBLT和HBLT可以在线性时间内完成初始化。用WBLT或HBLT描述的两个优先队列可在对数时间内合并为一个，而堆描述的优先队列无法做到。

接下来将介绍HBLT的操作，而WBLT的查找、插入、删除、合并和初始化操作与HBLT非常相似。

最大HBLT的插入

插入操作可借助于合并操作来完成。它可以通过先建立一棵仅包含待插入元素的HBLT，然后与原来的HBLT合并即可。

最大HBLT的删除

根是最大元素，如果跟被删除，将留下分别以其左右孩子为根的两棵HBLT的子树，将其合并到一起，便得到包含除删除元素外所有元素的最大HBLT。

合并两棵最大HBLT

具有$n$个元素的最大HBLT，其最右路径的长度为$O(logn)$。合并操作操作仅需遍历欲合并的HBLT的最右路径，即仅需移动右孩子。

合并策略最好用递归来实现。令$A,B$是需要合并的两棵最大HBLT，假设两者均不为空，为实现合并，首先需要检查两个根元素，较大者是合并后HBLT的根。假设$A$具有较大的根，且其左子树是$L$,$C$是由$A$的右子树与$B$合并而成的HBLT。所以$A,B$合并的结果是以$A$的根为根，$L,C$为左右子树的最大HBLT。如果$L$的$s$值小于$C$的$s$值，则$C$是右子树，$L$是左子树。

初始化最大HBLT

通过将$n$个元素插入到最初为空的最大HBLT中来进行初始化，所需时间是$O(logn)$。为得到具有线性时间的初始化算法，首先创建$n$个最大HBLT，每个树中仅包含$n$个元素中的某一个，这$n$棵树排成一个FIFO队列，然后从队列中依次删除两个HBLT，将其合并，然后再加入队列末尾，直到最后只有一棵HBLT。

类MaxHBLT

最大HBLT的每个节点均需要$data,LeftChild,RightChild和s$四个域，相应的节点类是$HBLTNode$,如下代码所示。

template<class T>
class MaxHBLT;

template<class T>
class HBLTNode{
    friend MaxHBLT<T>;
private:
    int s;
    T data;
    HBLTNode<T>* LeftChild, *RightChild;
public:
    HBLTNode(const T&e, const int sh){
        data = e;
        s = sh;
        LeftChild = RightChild = 0;
    }
};

而最大HBLT可用下面代码定义的类MaxHBLT来实现。类MaxHBLT的每个对象都有一个唯一的私有成员$root$，用来指向最大HBLT的根。构造函数在初始化时将其置为0，因此初始的最大HBLT是空。析构函数通过调用私有成员函数$Free$来删除HBLT中的所有节点，该函数按后序遍历整棵HBLT，每访问一个节点就删除该节点。

template<class T>
class MaxHBLT{
private:
    HBLTNode<T> *root;
    void PostOrder(void(*Visit)(HBLTNode<T>*u), HBLTNode<T>* t){
        // 后序遍历
        if (t){
            PostOrder(Visit, t->LeftChild);
            PostOrder(Visit, t->RightChild);
            Visit(t);
        }
    }
    static void free(HBLTNode<T>* t){
        delete t;
    }
    void Free(HBLTNode<T> *t){
        PostOrder(free, t);
        t = 0;
    }
    void Meld(HBLTNode<T> * &x, HBLTNode<T>* y);
public:
    MaxHBLT(){ root = 0 };
    ~MaxHBLT(){ Free(root); }
    T Max(){
        if (!root)
            throw OutOfBounds();
        return root->data;
    }
    MaxHBLT<T>& Insert(const T& x);
    MaxHBLT<T>& DeleteMax(T& x);
    MaxHBLT<T>& Meld(MaxHBLT<T>& x){
        Meld(root, x.root);
        x.root = 0;
        return *this;
    }
    void Initialize(T a[], int n);
};

接下来先给出合并操作的函数实现代码，该函数首先要处理合并的树中至少有一个为空的特殊情况。当没有空树时要确保$x$指向根值较大的树，如果$x$不是指向根值较大的树，则将$x$和$y$的指针进行交换。接下来把$x$的右子树与以$y$为根的最大HBLT进行递归合并。合并后为保证整棵树是最大HBLT，$x$的左右孩子可能需要交换，这是通过计算$x$的$s$值来确定的。

template<class T>
void MaxHBLT<T>::Meld(HBLTNode<T>* &x, HBLTNode<T>* y){
    // 合并两棵根分别是*x和*y的左高树，返回指向新根 x的指针
    if (!y)
        return;
    if (!x){
        x = y;
        return;
    }
    if (x->data < y->data){
        // 交换x和y
        HBLTNode<T> * temp = y;
        y = x;
        x = temp;
    }
    Meld(x->RightChild, y);
    if (!x->LeftChild){
        // 左子树为空,交换子树
        x->LeftChild = x->RightChild;
        x->RightChild = 0;
        x->s = 1;
    }
    else{
        if (x->LeftChild->s < x->RightChild->s){
            // 交换左右子树
            HBLTNode<T> * temp = x->LeftChild;
            x->RightChild = x->LeftChild;
            x->LeftChild = temp;
        }
        x->s = x->RightChild->s + 1;
    }
}

最后给出插入，删除和初始化函数的代码实现：

template<class T>
MaxHBLT<T>& MaxHBLT<T>::Insert(const T& x){
    // 将x插入左高树
    HBLTNode<T>* q = new HBLTNode<T>(x, 1);
    // 将q与原树合并
    Meld(root, q);
    return *this;
}

template<class T>
MaxHBLT<T>& MaxHBLT<T>::DeleteMax(T& x){
    // 删除最大元素，并将其放入x
    if (!root)
        throw OutOfBounds();

    x = root->data;
    HBLTNode<T>*L = root->LeftChild;
    HBLTNode<T>*R = root->RightChild;
    delete root;
    root = L;
    Meld(root, R);
    return *this;
}

template<class T>
void MaxHBLT<T>::Initialize(T a[], int n){
    // 初始化有n个元素的HBLT树
    Queue<HBLTNode<T>*>Q(n);
    // 删除老节点
    Free(root);
    for (int i = 1; i <= n; i++){
        HBLTNode<T>* q = new HBLTNode<T>(a[i-1], 1);
        Q.Add(q);
    }

    // 不断合并队列中的树；
    HBLTNode<T>*b, *c;
    for (int i = 1; i <= n - 1; i++) {
        Q.Delete(b).Delete(c);
        Meld(b, c);
        // 将合并后得到的树放入对了
        Q.Add(b);
    }

    if (n)
        Q.Delete(root);
}

对于上述函数的复杂性，构造函数只需要耗时$\theta(1)$,而析构函数需要$\theta(n)$，其中$n$是要删除的最大HBLT中的元素个数。Max函数的复杂性是$\theta(1)$，Insert,DeleteMax及共享成员函数Meld的复杂性与私有成员函数Meld的复杂性相同，由于私有成员函数Meld仅在以$x$和$y$为根的树的右子树中移动，因此其复杂性是$O(x->s+y->s)$。又由于$x$和$y$的最大$s$值分别为$log_2(m+1)$和$log_2(n+1)$,其中$m,n$分别是以$x$和$y$为根的最大HBLT中的元素个数，所以私有成员函数Meld的复杂性是$O(logmn)$。

更完整的代码例子可以查看最大高度优先左高树的实现。