优先级队列

发表于 分类于

此前的搜索树和词典结构都支持覆盖全集的访问和操作，其中存储的每一数据对象都可作为查找和访问目标。搜索树结构需要在所有元素之间定义并维护一个显式的全序关系，而词典结构从内部强制地在对象和对应的秩之间建立起某种关联关系，隐式地定义了一个全序关系。优先级队列将操作对象限定于当前的全局极值者。比如，在所有鸟类中，查找种群规模最小者。这一访问方式称为循优先级访问。

在实际应用环境中，不少事件都可用优先级队列描述，比如银行会员排队问题，操作系统的任务调度问题，输入法的词频调整。数据项的某种属性只要可以相互比较大小，则这种大小称为优先级。按照事先约定的优先级，可以始终高效地查找优先级最高的数据项的数据结构统一称为优先级队列。

考虑之前的数据结构效率

getmax() delmax() insert()
无序向量 $\Theta(n)$ $ \Theta(n)$ $O( 1 )$
有序向量 $O (1)$ $O (1)$ $O( n )$
无序列表 $\Theta ( n )$ $\Theta ( n )$ $O ( 1 )$
有序列表 $O (1)$ $O (1)$ $O( n )$

AVL、splay、red-black树三个接口均只需$O(logn)$时间，但是BBST的功能远远超出了优先级队列的要求。若只需查找极值元，则不必维护所有元素的全序关系，偏序足以。

完全二叉堆

有限偏序值的极值必定存在，此时借助堆结构维护一个全序即足矣。完全二叉堆即为堆结构的典型代表。

结构性与堆序性

首先结构性是在逻辑结构上须等同于完全二叉树，如此一来，堆节点和词条一一对应。其次，堆顶节点之外的每个节点都不大于其父节点，这即为堆序性。

由堆序性可以看出，堆中优先级最高的词条必然处于堆顶位置。因此，堆结构的getmax() 操作总是在堆顶完成。

完全二叉堆的拓扑联接结构完全由其规模$n$确定。按照层次遍历的顺序，每个节点都对应唯一的编号。故若将所有节点组织为一个向量，则堆中各节点与向量单元的秩必将一一对应。各节点在物理上连续排列，故仅需$O(n)$时间。通过节点的编号，可便捷地判断父子关系。

对于完全二叉堆中的任意节点$v$，必然满足：

  1. 若$v$有左孩子，则$i(lchild(v))=2i(v)+1$
  2. 若$v$有右孩子，则$i(rchild(v))=2i(v)+2$
  3. 若$v$有父节点，则$i(parent(v))=\lfloor (i(v)-1)/2 \rfloor=\lceil i(v)/2 \rceil -1$
1
2
3
4
#define  Parent(i)         ( ( i - 1 ) >> 1 ) //PQ[i]的父节点（floor((i-1)/2)，i无论正负）
#define  LChild(i)         ( 1 + ( ( i ) << 1 ) ) //PQ[i]的左孩子
#define  RChild(i)         ( ( 1 + ( i ) ) << 1 ) //PQ[i]的右孩子
#define  LastInternal(n)   Parent( n - 1 ) //最后一个内部节点（即末节点的父亲）

共$n$个节点时，内部节点的最大秩$=\lfloor (n-2)/2 \rfloor=\lceil (n-3)/2 \rceil$

令各节点的秩统一地递增一个单位，从秩的二进制表示来看，祖先必是后代的前缀。

对于秩为$r$的元素，其上溯第$h$代祖先所对应的秩必然为$O((r+1)>>h)-1)$

插入

为插入词条$e$,只需将$e$作为末元素接入向量，结构性自然保持，若堆序性亦未破坏，则完成。

若违反堆序性，则只能是与其父亲违反堆序性，$e$与其父节点交换，不断重复直到$e$与其父亲满足堆序性或者$e$到达堆顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> void PQ_ComplHeap<T>::insert ( T e ) { //将词条插入完全二叉堆中
   Vector<T>::insert ( e ); //首先将新词条接至向量末尾
   percolateUp ( _size - 1 ); //再对该词条实施上滤调整
}
//对向量中的第i个词条实施上滤操作，i < _size
template <typename T> Rank PQ_ComplHeap<T>::percolateUp ( Rank i ) {
   while ( ParentValid ( i ) ) { //只要i有父亲（尚未抵达堆顶），则
      Rank j = Parent ( i ); //将i之父记作j
      if ( lt ( _elem[i], _elem[j] ) ) break; //一旦当前父子不再逆序，上滤旋即完成
      swap ( _elem[i], _elem[j] ); i = j; //否则，父子交换位置，并继续考查上一层
   } //while
   return i; //返回上滤最终抵达的位置
}

效率

$e$与父亲的交换，每次仅需$O(1)$时间，每经过一次交换,$e$都会上升一层。在插入新节点$e$的过程中，只有$e$的祖先们才有可能需要与之交换。完全二叉堆以完全二叉树实现，必平衡，故$e$的祖先至多$O(logn)$个。

通过上滤，可在$O(logn)$时间内插入一个新节点，并整体得以调整为堆。

可在向量中将各节点顺次后移一个单元，并在腾出的元素中置入对应元素类型的最大值作为哨兵(比如，对于整数取作INT_MAX)。但在上滤过程中只需比较父子节点的大小，而无需核对是否越界。

如此转换后，父子节点各自在物理上所对应的秩需要进行调整

对于完全二叉堆中的任意节点$v$，必然满足：

  1. 若$v$有左孩子，则$i(lchild(v))=2i(v)$
  2. 若$v$有右孩子，则$i(rchild(v))=2i(v)+1$
  3. 若$v$有父节点，则$i(parent(v))=\lfloor i(v)/2 \rfloor=\lceil (i(v)-1)/2 \rceil $

在上滤的过程无需核对是否已经越界，因此在一定程度上提高插入操作的效率，但渐进复杂度仍然为$O(logn)$。当然，以上调整对下滤的过程及效率没有影响。

在堆顶通往任一叶节点的沿途上，各节点对应的关键码必然单调变化。所以可在引入新节点但未上滤调整之前，将该节点对应的查找路径视为一个静态查找表。并使用二分查找算法。

具体地，每次都可在$O(1)$时间内确定高度居中地祖先的秩，将其作为轴点，只需再做$O(1)$次比较，即可将查找范围缩小一半。如此反复迭代，直到查找范围内只剩下耽搁节点。

既然完全二叉堆的高度不超过$h=O(logn)$,故整个查找过程的迭代次数将不超过：

$logh=O(loglogn)$

以上算法只适用于上滤操作，因为任一节点通向其后代的路径并不唯一，而通往其祖先的路径必然唯一。

同时，以上方法可以有效地减少词条地比较操作，但是词条交换操作却不可减少。事实上，无论如何，再最坏情况下仍然需要执行$O( h )=O(logn)$次交换操作。

删除

最大元素始终在堆顶，删除堆顶元素只需要摘除向量首元素，以末元素$e$代替。若新堆顶$e$不满足堆序性，将$e$与其(至多)两个孩子中的大者交换。若与新孩子继续违反堆序性，则继续套用以上方法，不断重复，直到$e$满足堆序性，或已为叶子。

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T> T PQ_ComplHeap<T>::delMax() { //删除非空完全二叉堆中优先级最高的词条
   T maxElem = _elem[0]; _elem[0] = _elem[ --_size ]; //摘除堆顶（首词条），代之以末词条
   percolateDown ( _size, 0 ); //对新堆顶实施下滤
   return maxElem; //返回此前备份的最大词条
}
//对向量前n个词条中的第i个实施下滤，i < n
template <typename T> Rank PQ_ComplHeap<T>::percolateDown ( Rank n, Rank i ) {
   Rank j; //i及其（至多两个）孩子中，堪为父者
   while ( i != ( j = ProperParent ( _elem, n, i ) ) ) //只要i非j，则
      { swap ( _elem[i], _elem[j] ); i = j; } //二者换位，并继续考查下降后的i
   return i; //返回下滤抵达的位置（亦i亦j）
}

效率

在下滤的过程中，每经过一次交换，$e$的高度都将降低一层。故在每层至多需要一次交换。由于堆是完全二叉树，高度为$O(logn)$。通过下滤，可在$O(logn)$时间内删除堆顶节点并整体重新调整为堆。

若实际上升$k=O(logn)$层，则$k$次swap()操作共需$3k+1$次，可将此类赋值操作降低至$k+1$次。

在插入接口的上滤操作中，新元素可暂且不予插入，而只是将其上若干代祖先节点依次下移，待所有祖先均已就位时，才将新元素置入腾空的空节点。删除操作同理。

为何在摘除堆顶元素后，不自上而下地依次以更大孩子节点顶替空缺的父节点

如此可以维持完全二叉堆的堆序性，但是经过如此调整后完全二叉堆的拓扑结构未必仍然是一棵完全二叉树，故其结构性可能遭到破坏，因为该节点到最大孩子的路径和根节点到末节点的路径未必是同一条。

在关键码独立均匀分布时，插入操作平均只需常数时间

根据堆的定义及调整规则，若新节点$p$通过上滤升高了k层，则意味着在$2^{k+1}$个随机节点($p$的父亲、$p$、以及$p$的$2^{k+1}-2$)中，该节点恰好为第二大者。

于是，若将新节点$p$累计上升的高度记作H,则H恰好为$k$的概率为:

$Pr(H=k)=1/2^{k+1}=(1/2)^k(1/2),0\leq k$

这是一个典型的几何分布，其数学期望为：

$E(h)=1/(1/2)-1=1$

每个节点经过上滤后平均上升1层，其间需做$1+1=2$次比较操作。

建堆

很多算法中输入词条都是成批给出，故在初始化阶段往往需要解决一个共同问题:给定一组词条，高效地将他们组织为一个堆，这一过程称为建堆。

蛮力算法

从空堆开始，反复调用insert() 接口，即可将输入词条逐一插入其中，并最终完成建堆的任务。

若共有$n$个词条，则累计耗时量为：

$O(1)+O(2)+O(3)+…+O(n)=O(logn!)=O(nlogn)$

在$O(nlogn)$时间内可对所有词条全排序，但是在此只能提供一个偏序。

自上而下的下滤

1
2
3
4
template <typename T> void PQ_ComplHeap<T>::heapify ( Rank n ) { //Floyd建堆算法，O(n)时间
   for ( int i = 1; i<n; i-- ) //自底而上，依次
      percolateUp ( n, i ); //下滤各内部节点
}

效率

最坏情况下，每个节点都需要上滤至根，所需成本线性正比于其深度。即便只考虑底层，$n/2$个叶节点，深度均为$O(logn)$,累计耗时$O(nlogn)$，与蛮力算法一致。

考查高度为$h$，规模为$n=2^{h+1}-1$的满二叉树，其中深度为$i$的节点有$2^i$个，整个算法平均复杂度为：

$\sum_{i=1}^{n}(i2^i)=(h-1)2^{h+1}+2=(log_2(n+1)-2)(n+1)+2=O(nlogn)$

floyd算法

给定任意堆$H_0$和$H_1$，以及节点$p$，将其转化为一个新堆，相当于以$p$为中介将堆$H_1$,$H_2$ 合并，故称为堆合并操作。

为满足结构性，可将这两个堆作为p的左、右子树，联接成一棵完整的二叉树。若p与孩子满足堆序性，则该二叉树为一个不折不扣的二叉堆。此时等效于在delMax()中摘除堆顶，再将末位词条转移至堆顶。只需对堆顶p实施下滤操作即可将全树转换为堆

1
2
3
4
template <typename T> void PQ_ComplHeap<T>::heapify ( Rank n ) { //Floyd建堆算法，O(n)时间
   for ( int i = LastInternal ( n ); InHeap ( n, i ); i-- ) //自底而上，依次
      percolateDown ( n, i ); //下滤各内部节点
}

效率

每个内部节点所需的调整时间，正比于其高度而非深度。

不失一般性，考查满树$n=2^{d+1}-1$

$S(n)=$所有节点的高度总和

$\sum_{i=0}^{d} (d-i)(2^i)=d \sum_{i=0}^{d}2^i-T(n)$

$=d(2^{d+1}-1)-[(d-1)2^{d+1}+2]=2^{d+1}-(d+2)=n-log_2(n+1)=O(n)$

同层内部节点下滤的次序，仅涉及到其各自的后代，它们之间完全相互独立，故改变次序不影响最终的结果。同时，每个节点下滤过程完全不变，所需时间不变，建堆所需的总体时间亦不变。

具体应用

堆排序

完全二叉堆的另一具体应用：对于向量中的n个词条，如何借助堆的相关算法，实现高效的排序。相应地，这类算法也称作堆排序算法。

算法总体思路和选择排序相同，将所有词条分为未排序和已排序，不断从前一类中取出最大者，顺序加至后一类中。算法启动之初，所有词条均属于前者，此后，后一类不断增长。当所有词条转入后一类时，即完成排序。

1
2
3
4
5
template <typename T> void Vector<T>::heapSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
   PQ_ComplHeap<T> H ( _elem + lo, hi - lo ); //将待排序区间建成一个完全二叉堆，O(n)
   while ( ! H.empty() ) //反复地摘除最大元并归入已排序的后缀，直至堆空
      _elem[--hi] = H.delMax(); //等效于堆顶与末元素对换后下滤
}

这里的待排序词条既然组织为向量，不妨将其划分为前缀H和与之互补的后缀S。整个算法过程中始终满足以下不变性：H中的最大词条不会大于S中的最小词条。与选择排序不同之处在于，无论S包含多少词条，都将组织为一个堆。

不需要全排序，查找前$k$个元素所需的时间为$O(klogn)$。

效率

就地堆排序易于理解，便于实现，快速高效(尤其对于大规模数据)。

可就地运转，不需要全排序即可找出前k个词条，但是在采取就地策略的同时，对换操作必须涉及两个完整的词条，所以操作的单位成本增加。

以上堆排序算法是稳定的吗？

不是稳定的，在反复摘除堆顶并将末词条转移至堆顶，然后下滤过程中，雷同词条之间的相对次序不再保持，故它们在最终所得的排序队列中必然是随机排列的。

以上堆排序是堆排序固有的不足，难以通过算法自身的调整予以改进。可通过合成数方法，使得原来相等的元素，初始位置越靠前，合成数越小。

半无穷范围查询

所谓半无穷范围查询简化之前的一般性范围查询，查询区域为某一侧无界的矩形区域，比如$R=[-1,+1] [0,+\infty]$ ，即对称地包含正半$y$坐标轴、宽度为$2$的一个广义矩形区域。同样为从某一固定的点集中找出落在制定区域$R$内的所有点。通过优先级搜索可将保持$O(r+logn)$的时间效率并将空间复杂度从范围树的$O(nlogn)$优化至$O(n)$。

优先级搜索树除了在拓扑上应是一棵二叉搜索树，还需同时遵守以下三条规则：

  • 首先，各个节点的$y$坐标不小于其左、右孩子(如果存在)

    因此，整体上可视为以$y$为优先级的二叉堆

  • 此外，相对于任一父节点，左子树中的节点$x$坐标均不得大于右子树中的节点

  • 最后，互为兄弟的每一对左右子树，在规模上相差不得超过1

    若无需遵守最后一条规则，则可保证所有节点以$x$坐标为序组成一棵二叉搜索树，该结构兼具二叉搜索树和堆的特性，故亦称为树堆。

试设计一个算法，在$O(nlogn)$时间内将平面上$n$个点组织为一棵优先级搜索树

首先，不妨按照$x$坐标对所有点排序，然后根据以上定义，可以递归地将这些点组织为一棵优先级搜索树。

具体地，为了构造任一点集对应的子树，只需花费$O(n)$时间从中找到最高者($y$坐标最大者)。以下，借助$x$坐标的排序序列，可在$O(1)$时间内将剩余的$n-1$个点均平衡地划分为在空间上分列于左、右的两个子集–二者对应的子湖是可通过递归构造。

如此，构造全树的时间不超过:

$T(n)=2T(n/2)+O(n)=O(nlogn)$

试设计一个算法，利用已经创建的优先级搜索树，在$O(r+logn)$时间内完成每次半无穷范围查询

查询算法的大致过程可描述为

1
2
3
4
5
6
queryPST(PSTNode v,SemInfRange R){
     if(!v||v.y<R.y) return;//y-pruning
     if(R.x1<v.x&&v.x<R.x2) output(v);//hit
     if(R.x1<>v.xm) queryPST(v.lc,R);//recursion&x-pruning
     if(v.xm<=R.x2) queryPST(V.RC,R);//recursion&x-pruning
}

首先,根据$y$坐标，判断当前子树根节点$v$(及其后代)是否已经落在查询范围$R$之外。若是，则可立即在此处返回，不再进行递归—亦即纵向剪枝；否则，才需要继续深入查找。

以下，检查根节点$v$的$x$坐标，若落在查询范围之外，则需报告该节点。

最后，若在节点$v$处的横向切分位置为$xm$，则通过将其与$R$的左、右边界相比较，即可确认是否有必要继续沿对应的子树分支继续递归搜索–亦即横向剪枝。

唯有当$R.x1$不位于$v.xm$左侧时，才有必要对左子树$v.lc$做递归搜索，唯有当$R.x2$不位于$v.xm$左侧时，才有必要对右子树$v.rc$做递归搜索。

对任一查询区域$R=[R_1,R_2][y,+\infty]$ ,考查被算法queryPST()访问的任一节点，设与之对应的点为$v=(a,b)$，于是，$v$无非三种类型：

  1. 被访问，且报告出来，也就是说，$v$落在$R$之内$(x_1 \leq a \leq x_2)$且$y\leq b$，此类节点恰有$r$个
  2. 虽被访问，但未报告，因其$x$坐标落在$R$之外$(a<x_1)$或$(x_2<a)$而横向剪枝，不再深入递归。此类节点在每一层上至多有两个，总数不超过$2O(logn)$
  3. 虽然被访问，但是未被报告，$x$坐标落在$R$之内$(x_1 \leq a \leq x_2)$,但是因为其$y$坐标却未落在$R$之内$(b<y)$而纵向剪枝，此类节点的父节点必然属于1类或者2类，其总数不超过这两类节点总数的两倍。

综合以上分析可知，queryPST()算法渐进的时间复杂度不超过$O(r+logn)$。

锦标赛排序

堆排序中主要开销为建堆和删除堆顶元素，按照floyd算法，每次下滤可能在每一高度上均需要两次比较来从当前节点、当前节点的左、右孩子确定替换元素，所以在建堆过程中实际比较操作次数可能达到$2n$次，同理，删除堆顶元素并下滤恢复堆序性的过程中，堆的比较次数为$2logn$，以上两点均存在优化空间，所以引入了锦标赛排序，将前者比较操作次数降低至$n-1$次，后者比较操作次数降至$O(logn)$次。

锦标赛树

锦标赛树同样为二叉树，叶节点为待排序元素，以小者胜为原则，内部节点为孩子中的胜者，树根为全局冠军。内部节点之间存在重复，但是始终满足：在任一子树中，从根通往优胜者的沿途，所有节点都是优胜者。

由完全二叉树的性质，若存在$n$个叶节点，则内部节点为$n$个或者$n-1$个,取决于最后一个内部节点为一度还是二度。故节点总体空间不超过$2n$，空间复杂度为$O(n)$。

在每个内部节点处均需要一次比较，选出该节点左、右孩子中的胜者，所以构建锦标赛树所需的比较次数等于内部节点数目。所以构造锦标赛树的时间复杂度为$O(n)$。

插入/删除操作只需要更新沿着该叶节点到根节点的沿途节点，也即沿途胜者，总体时间复杂度为$O(logn)$。

由此设计锦标赛排序算法为

1
2
3
4
5
6
create a tournament tree for the input list
while there are active leaves
   remove the root
   retrace the root down to its leaf
   deactive the leaf
   replay along the path back to the root

先花费$O(n)$时间建立锦标赛树，然后删除根节点，并沿原胜利者到根节点的路径找到原胜利者的叶节点，将原胜利者的叶节点优先级置为无穷大。最后从叶节点出发，逐层上溯至树根，重新确定各轮胜者，耗时$O(logn)$。上述删除和重赛迭代n次，故锦标赛排序的总体时间复杂度为$O(nlog n)$。

败者树

由于在锦标赛树中，原冠军节点失效后，需要从该节点到根节点逐层上溯，重新确定各轮胜者，而重新确定胜者需要当前节点与其兄弟节点比较，但是其兄弟节点未必位于缓存中。除此之外，原来冠军已经失效，上溯过程中必然修改根节点到原来胜者所处叶节点沿途节点的值，均需要访存，所以引入败者树，父节点中不再保存胜者，而是保存败者。按照锦标赛排序算法，从根节点下行找到冠军叶节点，此时只访问该路径上的节点，所以具有时间局部性，可以更充分地利用缓存机制，在败者树更新过程中，各沿途节点未必需要更新，减少了写操作。

锦标赛树可否实现稳定排序？

可以，只需保证在相等元素比较时，位置靠前者胜出即可，得到地排序序列仍然可以保持相等元素之间的相对次序。

另外，可借助多叉锦标赛树实现多路合并。

左式堆

除了标准的插入和删除操作，堆结构在实际应用中的另一常见操作即为合并。任给堆A和B，如何将二者所含的词条组织为一个堆H。

方法一

反复地取出堆B的最大词条并插入堆A中，当堆B为空时，堆A即为所需的堆H,这一过程可描述为：

1
2
while(!B.empty())
   A.insert(B.delmax());

将两个堆的规模分别记作$n$和$m$,且$n\geq m$。每一步迭代均需做一次删除和一次插入操作。因共需$m$次迭代，故总体运行时间为：$m[O(logm)+log(n+m)]=O(mlog(n+m))=O(mlogn)$

方法二

将两个堆中的词条视为彼此独立的对象，直接借助floyd算法，将它们重新组织为一个新堆H,该方法的运行时间为：$O(n+m)$

实际上，既然所有词条已分成两组各自成堆，则意味着它们已经具有一定的偏序性，而一组相互独立的词条并不具有偏序性。由前者构建一个更大的偏序集，应该比后者简单。以上算法均未凑效的原因在于，不能保证合并操作涉及的节点足够少。

单侧倾斜

左式堆是优先级队列的另一表现形式，可高效地支持合并操作。其基本思路是：在保持堆序性的前提下附加新的条件，使在堆的合并过程中，只需要调整很少量的节点。具体地，调整节点不超过$O(logn)$个，故可达到极高的效率。

左式堆的整体结构呈单侧倾斜状，其中节点均偏向于左侧，也就是说，左式堆不再如完全二叉堆一样满足结构性。实际上，结构性并非堆结构的本质要求。

空节点路径长度

左式堆的倾斜度，应该控制在什么范围？又该如何控制？为此，借鉴红黑树和AVL树，未各节点引入空节点路径长苏，并依次确定相关算法的执行方向。

节点x的空节点路径长度(null path length)，记为$npl(x)$。若$x$为外部节点，则约定$npl(x)=npl(null)=0$。若x为内部节点，则$npl(x)$可递归地定义为：$npl(x)=1+min(npl(lc(x)),npl(rc(x)))$

也就是说，节点$x$的$npl$值取决于其左、右孩子$npl$值中的小者。

左倾性

左式堆是处处满足左倾性的二叉堆，即任一内部节点满足：

$npl(lc(x))\geq npl(rc(x))$

也就是说，就$npl$的指标而言，任一内部节点的左孩子都不小于其右孩子。

根据$npl$和左倾性的定义，左式堆中任一节点$x$都应满足：

$npl(x)=1+npl(rc(x))$

左式堆中每个节点的$npl$值，仅取决于其右孩子。

左孩子的$npl$值不小于右孩子并不意味着左孩子的高度必定不低于右孩子，因为一个节点的$npl$值由子树中最浅的叶子决定，高度则由最深的叶子决定。

右侧链

从节点$x$出发沿右侧分支一直前行至空节点，经过的通路称作其最右侧通路，记作rPath(x)。在左式堆中，每个节点的npl值恰好等于其最右侧通路的长度。

根节点r的最右侧通路rPath(r)的终点必然为全堆中深度最小的外部节点。若记：

$npl(r)=|rPath(x)|=d$

则该堆应包含一棵以$r$为根、高度为$d$的满二叉树，该二叉树至少应包含$2^{d}-1$个内部节点，$2^{d+1}-1$个外部节点。反之，在包含$n$个节点的左式堆中，最右侧通路$d\leq \lfloor log_2(n+1)-1 \rfloor =O(logn)$

合并

首先判断并处理待合并子堆为空的平凡情况，再通过一次比较，以及在必要时所做的一次交换，以保证堆顶a的优先级总是不低于另一堆顶$b$。

按照上述原理递归地将$a$的右子堆和堆$b$合并，并作为$a$的右子堆重新接入。递归返回后，还需比较$a$左、右孩子的npl值，如有必要还需令其互换，以保证前者不小于后者。此后只需在右孩子npl的基础上加1即可得到堆顶$a$的新npl值。

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T> //根据相对优先级确定适宜的方式，合并以a和b为根节点的两个左式堆
static BinNodePosi(T) merge ( BinNodePosi(T) a, BinNodePosi(T) b ) {
   if ( ! a ) return b; //退化情况
   if ( ! b ) return a; //退化情况
   if ( lt ( a->data, b->data ) ) swap ( a, b ); //一般情况：首先确保b不大
   a->rc = merge ( a->rc, b ); //将a的右子堆，与b合并
   a->rc->parent = a; //并更新父子关系
   if ( !a->lc || a->lc->npl < a->rc->npl ) //若有必要
      swap ( a->lc, a->rc ); //交换a的左、右子堆，以确保右子堆的npl不大
   a->npl = a->rc ? a->rc->npl + 1 : 1; //更新a的npl
   return a; //返回合并后的堆顶
} //本算法只实现结构上的合并，堆的规模须由上层调用者负责更新

复杂度

借助递归分析图不难看出，所有递归实例可排成一个线性序列，实质上属于线性递归，其运行时间正比于递归深度。递归只可能发生在两个待合并子树的最右侧通路上。若待合并堆的规模分别为$n$和$m$，则其两条最右侧通路的长度分别不会超过：

$O(logn)+O(logm)=O(logn+logm)=O(log (max(n,m))$

删除

基于merge操作实现delMax()算法，考查堆顶$x$及其子堆$H_L$和$H_R$。

在摘除x之后，$H_L$和$H_R$即可被视作为两个彼此独立待合并的堆。于是，只要通过merge()操作将它们合并起来，效果完全等效于常规的delMax()操作。

1
2
3
4
5
6
7
8
template <typename T> T PQ_LeftHeap<T>::delMax() { //基于合并操作的词条删除算法（当前队列非空）
   BinNodePosi(T) lHeap = _root->lc; //左子堆
   BinNodePosi(T) rHeap = _root->rc; //右子堆
   T e = _root->data; delete _root; _size--; //删除根节点
   _root = merge ( lHeap, rHeap ); //原左右子堆合并
//   if ( _root ) _root->parent = NULL; //若堆非空，还需相应设置父子链接
   return e; //返回原根节点的数据项
}

由合并操作的分析，时间成本总体依然不超过$O(log n)$

插入

若将词条$x$插入堆H中，只要将$x$视为一个仅含单个节点的堆，则调用merge()操作后，其效果等效于完成了一次词条插入操作。

1
2
3
4
5
6
template <typename T> void PQ_LeftHeap<T>::insert ( T e ) { //基于合并操作的词条插入算法
   BinNodePosi(T) v = new BinNode<T> ( e ); //为e创建一个二叉树节点
   _root = merge ( _root, v ); //通过合并完成新节点的插入
//   _root->parent = NULL; //既然此时堆非空，还需相应设置父子链接
   _size++; //更新规模
}

由合并操作的分析，时间成本总体依然不超过$O(log n)$

栈堆/队堆

为栈/队列提供在$O(1)$时间内访问最大值的接口，集成了栈/队列和堆属性的数据结构，称为栈堆(steap)/队堆(queap)。

栈堆

对于任何一个栈，可以引入另一个与之孪生的镜像P，P中的元素与S中的元素始终保持一一对应，前者的取值恰好是后者所有前驱中的最大者。当然P中元素必定按照单调非降的顺序排列。如此，任何时刻栈P的顶元素，都是栈S中的最大元素。为保持二者如上的对应关系，它们的push和pop必须同步进行。

若执行S.pop()，则只需同步地执行H.pop()，而若执行S.push(e),则需要同步地执行P.push(max(e,P.top()))。

以上方案还可以进一步优化。

可将栈P的空间进一步压缩，P中相等的元素必然彼此相邻，并因此可分为若干组。若假想式地令栈P中的每个元素通过指针指向栈S中的每个元素，而不是保留后者的副本，则可以将同组的元素合并起来，共享一个指针。当然，同时还需为合并后的元素增设一个计数器，记录原先同组元素的数目。如此改进之后，每一组元素只需保留以分，附加空间使用量可以大大降低。

相应地，在栈S每次执行出栈操作时，栈P必须同步地执行：

1
if(!(--P.top().counter)) P.pop();

而在栈S每次入栈时，栈P必须同步地执行

1
P.top()<e ? P.push(e),P.top.counter=1 :P.top().counter++;

可见，S的push()和pop()接口，依然保持$O(1)$效率。

队堆

上述关于栈的技巧同样可以推广至队列结构，可以引入一个双端队列P，并依然约定，其中每个元素也是始终指向队列Q中所有前驱的最大者。

为保持二者的对应关系，它们的dequeue()和enqueue()接口必须同步进行，若执行：Q.dequeue(),则需同步地执行P.removeFront()，而若执行Q.enqueue()，则只需同步地执行：

1
2
3
4
P.insertRear(e);
for(x=P.rear();x&(x.key<=e);x=x.pred){
  x.key=e;
}

除了首先令e加入队列P，还需要将P尾部所有不大于e的元素统一更新为e。在最坏情况下，这需要$\Omega(n)$时间，而这种情况可能持续发生。造成这一困难的原因在于，队列中任一元素的前驱集，不再如栈中那样是固定的，而是可能增加，且新增元素可能非常大。

同样，可仿照前一技巧，将队列P压缩。然后在队列每次执行出队操作时，队列P必须同步地执行：

1
if(!(--P.front().counter)) P.removeFront();

而在队列Q每次执行入队时，队列P同步地执行：

1
2
3
4
5
a=1;
while(!P.empty()&&(P.rear().key<=e))
   a+=P.removeRear().counter;//当当前尾部元素不大于e时，累计计数器后删除该尾部元素
P.insertRear(e);
P.rear().counter=a;

这里的while循环在最坏情况下仍然需要迭代$O(n)$步，但因为参与迭代的元素必然随即被删除，故就分摊意义而言仅为$O(1)$步，时间性能大为改善。

另外，这里的队列P并不需要双端队列的所有功能，removeFront(),insertRear(),removeRear()接口，无需使用insertFront()接口。