《第1章数据结构》由会员分享，可在线阅读，更多相关《第1章数据结构（45页珍藏版）》请在金锄头文库上搜索。
1、高等数据结构与算法 优先队列 骆嘉伟计算机与通信学院湖南大学Jt ljw 2020 6 15 1 DataMining ConceptsandTechniques 1引言 定义 优先队列 优先队列 priorityqueue 是0个或多个元素的集合 每个元素都有一个优先权或值 对优先队列执行的操作有1 查找 2 插入一个新元素 3 删除 最小优先队列 minpriorityqueue 查找操作用来搜索优先权最小的元素 删除操作用来删除该元素最大优先队列 maxpriorityqueue 查找操作用来搜索优先权最大的元素 删除操作用来删除该元素 引言 2020 6 15 2 DataMining
2、 ConceptsandTechniques 1引言 最大优先队列的抽象数据类型描述抽象数据类型MaxPriorityQueue 实例有限的元素集合 每个元素都有一个优先权操作Create 创建一个空的优先队列Size 返回队列中的元素数目Max 返回具有最大优先权的元素Insert x 将x插入队列DeleteMax x 从队列中删除具有最大优先权的元素 并将该元素返回至x 引言 2020 6 15 3 DataMining ConceptsandTechniques 2线性表 采用无序线性表假设有一个具有n个元素的优先队列 那么插入操作可以十分容易地在表的右端末尾执行 插入所需时间为 1
3、删除操作时必须查找优先权最大的元素 即在未排序的n个元素中查找具有最大优先权的元素 所以删除操作所需时间为 n 如果利用链表 插入操作在链头执行 时间为 1 而每个删除操作所需时间为 n 采用有序线性表元素按递增次序排列 使用链表时则按递减次序排列 这两种描述方法的删除时间均为 1 插入操作所需时间为 n 线性表 2020 6 15 4 DataMining ConceptsandTechniques 3堆 定义 最大树 最小树 每个节点的值都大于 小于 或等于其子节点 如果有的话 值的树 堆 2020 6 15 5 DataMining ConceptsandTechniques 3堆 定义
4、 最大堆 最小堆 最大 最小 的完全二叉树 堆 2020 6 15 6 DataMining ConceptsandTechniques 3堆 最大堆的插入 堆 2020 6 15 7 DataMining ConceptsandTechniques 3堆 最大堆的删除 堆 2020 6 15 8 DataMining ConceptsandTechniques 3堆 最大堆的初始化 堆 2020 6 15 9 DataMining ConceptsandTechniques 9 3堆 堆 2020 6 15 10 DataMining ConceptsandTechniques 3堆 类Ma
5、xHeaptemplateclassMaxHeap public MaxHeap intMaxHeapSize 10 MaxHeap delete heap intSize const returnCurrentSize TMax if CurrentSize 0 throwOutOfBounds returnheap 1 MaxHeap 元素数组 堆 2020 6 15 11 DataMining ConceptsandTechniques 3堆 最大堆的插入templateMaxHeap 堆 2020 6 15 12 DataMining ConceptsandTechniques 3堆
6、最大堆的删除templateMaxHeap i的孩子 堆 2020 6 15 13 DataMining ConceptsandTechniques 3堆 while ci heap ci break 能 不能heap i heap ci 将孩子上移i ci 下移一层ci 2 heap i y return this 堆 2020 6 15 14 DataMining ConceptsandTechniques 3堆 初始化一个非空最大堆templatevoidMaxHeap Initialize Ta intsize intArraySize 把最大堆初始化为数组a delete heap
7、heap a CurrentSize size MaxSize ArraySize 产生一个最大堆for inti CurrentSize 2 i 1 i Ty heap i 子树的根 寻找放置y的位置 堆 2020 6 15 15 DataMining ConceptsandTechniques 3堆 intc 2 i c的父节点是y的目标位置while c heap c break 能 不能heap c 2 heap c 将孩子上移c 2 下移一层heap c 2 y 堆 2020 6 15 16 DataMining ConceptsandTechniques 4左高树 一棵二叉树 它有
8、一类特殊的节点叫做外部节点 用来代替树中的空子树 其余节点叫做内部节点 增加了外部节点的二叉树被称为扩充二叉树 令s x 为从节点x到它的子树的外部节点的所有路径中最短的一条 根据s x 的定义可知 若x是外部节点 则s的值为0 若x为内部节点 则它的s值是 min s L s R 1其中L与R分别为x的左右孩子 定义 高度优先左高树 当且仅当一棵二叉树的任何一个内部节点 其左孩子的s值大于等于右孩子的s值时 该二叉树为高度优先左高树 height biasedleftisttree HBLT 左高树 2020 6 15 17 DataMining ConceptsandTechniques
9、4左高树 左高树 2020 6 15 18 DataMining ConceptsandTechniques 4左高树 定义 最大HBLT 即同时又是最大树的HBLT 定义 最小HBLT 即同时又是最小树的HBLT 定义 重量优先左高树 当且仅当一棵二叉树的任何一个内部节点 其左孩子的w值大于等于右孩子的w值时 该二叉树为重量优先左高树 weight biasedleftisttree WBLT 定义 最大 小 WBLT 即同时又是最大 小 树的WBLT 左高树 2020 6 15 19 DataMining ConceptsandTechniques 4左高树 合并策略 令A B为需要合并的
10、两棵最大HBLT 如果其中一个为空 则将另一个作为合并的结果 因此可以假设两者均不为空 为实现合并 先比较两个根元素 较大者作为合并后的HBLT的根 假定A具有较大的根 且其左子树为L C是由A的右子树与B合并而成的HBLT A与B合并所得结果即是以A的根为根 L与C为左右子树的最大HBLT 如果L的s值小于C的s值 则C为左子树 否则L为左子树 左高树 2020 6 15 20 DataMining ConceptsandTechniques 4左高树 左高树 2020 6 15 21 DataMining ConceptsandTechniques 4左高树 左高树 2020 6 15 2
11、2 DataMining ConceptsandTechniques 4左高树 初始化最大HBLT首先创建n个最大HBLT 每个树中仅包含n个元素中的某一个 这n棵树排成一个FIFO队列 然后从队列中依次删除两个HBLT 将其合并 然后再加入队列末尾 直到最后只有一棵HBLT 左高树 2020 6 15 23 DataMining ConceptsandTechniques 4左高树 构造具有五个元素 7 1 9 11 2的一棵最大HBLT 为此 首先构造五个单元素的最大HBLT 并形成一个FIFO队列 把最前面的两个最大HBLT7和1从队列中删除并进行合并 所得结果如图a所示 将该结果加入到
12、队列中 接下来从队列中删除两棵最大HBLT9和11并进行合并 所得结果如图b所示 也将该结果加入队列中 现在继续从队列中删除最大HBLT2及图a所得到的HBLT 并进行合并 所得结果如图c所示加入队列 下一对从队列中删除的最大HBLT如图b与c所示 经合并得到的最大HBLT如图d所示 将该结果插入到队列中 至此 队列中只有一棵最大HBLT 初始化工作完成 左高树 2020 6 15 24 DataMining ConceptsandTechniques 4左高树 HBLT的节点类templateclassHBLTNode friendMaxHBLT public HBLTNode constT
13、 左高树 2020 6 15 25 DataMining ConceptsandTechniques 4左高树 MaxHBLT类templateclassMaxHBLT public MaxHBLT root 0 MaxHBLT Free root TMax if root throwOutOfBounds returnroot data MaxHBLT 左高树 2020 6 15 26 DataMining ConceptsandTechniques 4左高树 合并两棵左高树templatevoidMaxHBLT Meld HBLTNode 左高树 2020 6 15 27 DataMini
14、ng ConceptsandTechniques 4左高树 if x LeftChild 左子树为空 交换子树x LeftChild x RightChild x RightChild 0 x s 1 else 检查是否需要交换子树if x LeftChild sRightChild s Swap x LeftChild x RightChild x s x RightChild s 1 左高树 2020 6 15 28 DataMining ConceptsandTechniques 4左高树 最大HBLT的插入templateMaxHBLT 左高树 2020 6 15 29 DataMin
15、ing ConceptsandTechniques 5应用1 堆排序 先将要排序的n个元素初始化为一个最大堆 然后每次从堆中提取 即删除 元素 各元素将按递减次序排列 templatevoidHeapSort Ta intn 利用堆排序算法对a 1 n 进行排序 创建一个最大堆MaxHeapH 1 H Initialize a n n 从最大堆中逐个抽取元素Tx for inti n 1 i 1 i H DeleteMax x a i 1 x 在堆的析构函数中保存数组aH Deactivate 堆排序 2020 6 15 30 DataMining ConceptsandTechniques
16、5应用2 霍夫曼编码 主要用途是实现数据压缩 设给出一段报文 CASTCASTSATATATASA字符集合是 C A S T 各个字符出现的频度 次数 是W 2 7 4 5 若给每个字符以等长编码A 00T 10C 01S 11则总编码长度为 2 7 4 5 2 36 若按各个字符出现的概率不同而给予不等长编码 可望减少总编码长度 因各字符出现的概率为 2 18 7 18 4 18 5 18 霍夫曼编码 2020 6 15 31 DataMining ConceptsandTechniques 5应用2 霍夫曼编码 霍夫曼树中左分支赋0 右分支赋1 得霍夫曼编码 变长编码 A 0T 10C 110S 111它的总编码长度 7 1 5 2 2 4 3 35 比等长编码的情形要短 总编码长度正好等于霍夫曼树的带权路径长度WPL 霍夫曼编码是一种无前缀编码 解码时不会混淆 霍夫曼编码 2020 6 15 32 DataMining ConceptsandTechniques 5应用2 霍夫曼编码 带权路径长度 WeightedPathLength WPL 树的带权路径长度是树的各叶结点所带的
