根据数据对象之间相对优先级对其进行访问的方式#xff0c;与此前的访问方式有着本质区别#xf…概述

按照事先约定的优先级可以始终高效查找并访问优先级最高数据项的数据结构也统称作优先级队列

根据数据对象之间相对优先级对其进行访问的方式与此前的访问方式有着本质区别称作

循优先级访问

“全局极值”本身就隐含了“所有元素可相互比较”这一性质。

然而优先级队列并不一定需要动态维护这个全序却转而维护一个偏序partial

因此优先级队列不仅足以高效地支持仅针对极值对象的接口操作更可有效地控制整体计算成本。

基本实现

优先级队列作为一类独特数据结构的意义在于通过转而维护词条集的一个偏序关系。

操作接口

操作结构功能描述size()报告优先级队列的规模即其中词条的总数insert()将指定词条插入优先级队列getMax()返回优先级最大的词条若优先级队列非空delMax()删除优先级最大的词条若优先级队列非空

接口定义

}因为这一组基本的ADT接口可能有不同的实现方式故这里均以虚函数形式统一描述这些接口以便在不同的派生类中具体实现。

借助无序列表、有序列表、无序向量或有序向量都难以同时兼顾insert()和delMax()操作的高效率。

完全二叉堆结构

堆中优先级最高的词条必然始终处于堆顶位置。

因此堆结构的getMax()操作总是可以在O(1)时间内完成。

结构等同于完全二叉树n

insert()和delMax()操作的时间复杂度将线性正比于堆的高度h故它们均可在O(logn)的时间内完成。

完全二叉堆的拓扑联接结构完全由其规模n确定。

节点在物理上连续排列故总共仅需O(n)空间而且利用各节点的编号或秩也可便捷地判别父子关系。

#include

public:PQ_ComplHeap()[}//默认构造PQ_ComplHeap

Rank

CompIHeap全局优先级最高的词条总是位于堆顶只需返回向量的首单元即可在O(1)时间内完成getMax()操作。

templatetypename

}尽管此时如图(a)所示新词条的引入并未破坏堆的结构性但只要新词条e不是堆顶就有可能与其父亲违反堆序性。

所以需要对新接入的词条做适当调整在保持结构性的前提下恢复整体的堆序性。

i(p)

e≤p则堆序性在此局部以至全堆均已满足插入操作因此即告完成。

反之若

互换位置。

如图(b)所示如此不仅全堆的结构性依然满足而且e和p之间的堆序性也得以恢复。

当然此后e与其新的父亲可能再次违背堆序性。

若果真如此继续套用以上方法如图(

每交换一次新词条e都向上攀升一层故这一过程也形象地称作上滤percolate

_size

//否则父子交换位置并继续考查上一层}//whilereturn

log2

n。

而在向量中每次交换操作只需常数时间故上滤调整乃至整个词条插入算法整体的时间复杂度均为

在如图(a)所示由5个元素组成的初始完全堆中现拟插入关键码为5的新元素。

为此首先如图(b)所示将该元素置于向量的末尾。

此时新元素5与其父节点0逆序故如图©所示经一次交换之后新元素5上升一层。

此后新元素5与其新的父节点4依然逆序故如图(d)所示经一次交换后再上升一层。

此时因已抵达堆顶插入操作完毕故算法终止。

_size

删除算法也分为两个步骤1.待删除词条r总是位于堆顶可直接将其取出并备份2.摘除堆顶首词条)代之以末词条对新堆顶实施下滤将最末尾的词条e转移至堆顶。

template

)所示将e与其(至多)两个孩子中的大者(图中深色节点交换位置。

与上滤一样由于使用了向量来实现堆根据词条e的秩可便捷地确定其孩子的秩。

此后堆中可能的缺陷依然只能来自于词条e——它与新孩子可能再次违背堆序性。

若果真如此继续套用以上方法将e与新孩子中的大者交换结果如图(d)所示。

实际上只要有必要此后可如图(e)和(f)不断重复这种交换操作。

因每经过一次交换词条e都会下降一层故这一调整过程也称作下滤percolate

//对向量前

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

具体地若共有n个词条则共需迭代n次。

第k轮迭代耗时O(logk)故累计耗时间量应为O(log1

log2

自上而下的上滤对任何一棵完全二叉树只需自顶而下、自左向右地针对其中每个节点实施一次上滤即可使之成为完全二叉堆。

在此过程中为将每个节点纳入堆中所需消耗的时间量将线性正比于该节点的深度O(nlogn)。

Floyd

此时的场景完全等效于在delMax()操作中摘除堆顶再将末位词条

(p)

自底而上地反复套用可不断地将处于下层的堆捉对地合并成更高一层的堆并最终得到一个完整的堆。

Floyd

}只需自下而上、由深而浅地遍历所有内部节点并对每个内部节点分别调用一次下滤算法percolateDown()。

复杂度

算法依然需做n步迭代以对所有节点各做一次下滤。

这里每个节点的下滤所需的时间线性正比于其高度故总体运行时间取决于各节点的高度总和。

2^{h1}

由于在遍历所有词条之前绝不可能确定堆的结构故以上已是建堆操作的最优算法。

各节点所消耗的时间线性正比于其深度——而在完全二叉树中深度小的节点远远少于高度小的节点。

堆排序

将所有词条分成未排序和已排序两类不断从前一类中取出最大者顺序加至后一类中。

算法启动之初所有词条均属于前

将其划分为前缀H和与之互补的后缀S分别对应于上述未排序和已排序部分。

与常规选择排序算法一样在算法启动之初H覆盖所有词条而S为空。

新算法的不同之处在于整个排序过程中无论H包含多少词条始终都组织为一个堆。

H中的最大词条不会大于S中的最小词条——除非二者之一为空比如算法的初始和终止时刻。

首先如图(a)取出首单元词条M将其与末单元词条x交换。

M既是当前堆中的最大者同时根据不变性也不大于S中的任何词条故如此交换之后M必处于正确的排序位置。

如图(b)此时可等效地认为S向前扩大了一个单元H相应地缩小了一个单元。

请注意如此重新分界之后的H和S依然满足以上不变性。

至此,唯一尚未解决的问题是词条x通常不能“胜任”堆顶的角色。

最后如图(c

在每一步迭代中交换M和X只需常数时间对x的下滤调整不超过O(logn)时间。

因此全部n步迭代累计耗时不超过O(nlogn)。

即便使用蛮力算法而不是Floyd算法来完成H的初始化整个算法的运行时间也不超过O(nlogn)。

template

//反复地摘除最大元并归入已排序的后缀直至堆空_elem[--hi]

H.delMax(

m×[O(logm)O(log(nm))]O(mlog(nm))O(mlogn)

Floyd

基本思路在保持堆序性的前提下附加新的条件使得在堆的合并过程中只需调整很少量的节点。

具体地需参与调整的节点不超过O(logn)个故可达到极高的效率。

左式堆的整体结构呈单侧倾斜状依照惯例其中节点的分布均偏向左侧。

也就是说左式堆将不再如完全二叉堆那样满足结构性。

#include

//Po_LeftHeapPQ_LeftHeap首先继承了优先级队列对外的标准ADT接口。

另外既然左式堆的逻辑结构已不再等价于完全二叉树改用紧凑性稍差、灵活性更强的二叉树结构将更具针对性。

其中蛮力式批量构造方法耗时O(nlogn)利用Floyd算法可改进至O(n)。

空节点路径长度

length记作npl(x)。

若x为外部节点则约定npl(x)

npl(null)

0。

反之若x为内部节点则npl(x)可递归地定义为npl(x)

min(

npl(x)既等于x到外部节点的最近距离同时也等于以x为根的最大满子树的高度。

左倾性与左式堆

左式堆左孩子的npl值不小于右孩子而前者的高度却可能小于后者。

左式堆中任一内节点x都应满足npl(x)

从x出发沿右侧分支一直前行直至空节点经过的通路称作其最右侧通路记作rPath(x)。

npl(r)

//根据相对优先级确定适宜的方式合并以a和b为根节点的两个左式堆

static

//算法只实现结构上的合并首先判断并处理待合并子堆为空的平凡情况。

然后再通过一次比较以及在必要时所做的一次交换以保证堆顶a的优先级总是不低于另一堆顶b。

递归地将a的右子堆与堆b合并并作为a的右子堆重新接入。

递归返回之后还需比较此时a左、右孩子的npl值如有必要还需令其互换以保证前者不小于后者。

此后只需在右孩子npl值的基础上加一即可得到堆顶a的新npl值。

至此合并方告完成。

复杂度

若待合并堆的规模分别为n和m则其两条最右侧通路的长度分别不会超过O(logn)和O(logm)因此合并算法总体运行时间应不超过O(logn)

O(logm)

于是只要通过merge()操作将它们合并起来则其效果完全等同于一次常规的delMax()删除操作。

template

//基于合并操作的词条删除算法当前队列非空)BinNodePosi(T)

lHeap

}时间成本主要消耗于对merge()的调用总体依然不超过O(logn)。

基于堆合并操作实现词条插入算法

只要将x也视作仅含单个节点的堆则通过调用merge()操作将该堆与堆H合并之后其效果即完全等同于完成了一次词条插入操作。

template

}时间成本主要也是消耗于对merge()的调用总体依然不超过O(logn)