




已阅读5页,还剩40页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
高等数据结构与算法:优先队列,骆嘉伟计算机与通信学院湖南大学Jt_ljw,2020/5/26,1,DataMining:ConceptsandTechniques,1引言,定义优先队列优先队列(priorityqueue)是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1)查找;2)插入一个新元素;3)删除。最小优先队列(minpriorityqueue):查找操作用来搜索优先权最小的元素,删除操作用来删除该元素最大优先队列(maxpriorityqueue):查找操作用来搜索优先权最大的元素,删除操作用来删除该元素。,引言,2020/5/26,2,DataMining:ConceptsandTechniques,1引言,最大优先队列的抽象数据类型描述抽象数据类型MaxPriorityQueue实例有限的元素集合,每个元素都有一个优先权操作Create():创建一个空的优先队列Size():返回队列中的元素数目Max():返回具有最大优先权的元素Insert(x):将x插入队列DeleteMax(x):从队列中删除具有最大优先权的元素,并将该元素返回至x,引言,2020/5/26,3,DataMining:ConceptsandTechniques,2线性表,采用无序线性表假设有一个具有n个元素的优先队列,那么插入操作可以十分容易地在表的右端末尾执行,插入所需时间为(1)。删除操作时必须查找优先权最大的元素,即在未排序的n个元素中查找具有最大优先权的元素,所以删除操作所需时间为(n)。如果利用链表,插入操作在链头执行,时间为(1),而每个删除操作所需时间为(n)。采用有序线性表元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为(1),插入操作所需时间为(n)。,线性表,2020/5/26,4,DataMining:ConceptsandTechniques,3堆,定义最大树(最小树)每个节点的值都大于(小于)或等于其子节点(如果有的话)值的树。,堆,2020/5/26,5,DataMining:ConceptsandTechniques,3堆,定义最大堆(最小堆)最大(最小)的完全二叉树。,堆,2020/5/26,6,DataMining:ConceptsandTechniques,3堆,最大堆的插入,堆,2020/5/26,7,DataMining:ConceptsandTechniques,3堆,最大堆的删除,堆,2020/5/26,8,DataMining:ConceptsandTechniques,3堆,最大堆的初始化,堆,2020/5/26,9,DataMining:ConceptsandTechniques,9.3堆,堆,2020/5/26,10,DataMining:ConceptsandTechniques,3堆,类MaxHeaptemplateclassMaxHeappublic:MaxHeap(intMaxHeapSize=10);MaxHeap()deleteheap;intSize()constreturnCurrentSize;TMax()if(CurrentSize=0)throwOutOfBounds();returnheap1;MaxHeap/元素数组,堆,2020/5/26,11,DataMining:ConceptsandTechniques,3堆,最大堆的插入templateMaxHeap,堆,2020/5/26,12,DataMining:ConceptsandTechniques,3堆,最大堆的删除templateMaxHeap/i的孩子,堆,2020/5/26,13,DataMining:ConceptsandTechniques,3堆,while(ci=heapci)break;/能/不能heapi=heapci;/将孩子上移i=ci;/下移一层ci*=2;heapi=y;return*this;,堆,2020/5/26,14,DataMining:ConceptsandTechniques,3堆,初始化一个非空最大堆templatevoidMaxHeap:Initialize(Ta,intsize,intArraySize)/把最大堆初始化为数组a.deleteheap;heap=a;CurrentSize=size;MaxSize=ArraySize;/产生一个最大堆for(inti=CurrentSize/2;i=1;i-)Ty=heapi;/子树的根/寻找放置y的位置,堆,2020/5/26,15,DataMining:ConceptsandTechniques,3堆,intc=2*i;/c的父节点是y的目标位置while(c=heapc)break;/能/不能heapc/2=heapc;/将孩子上移c*=2;/下移一层heapc/2=y;,堆,2020/5/26,16,DataMining:ConceptsandTechniques,4左高树,一棵二叉树,它有一类特殊的节点叫做外部节点,用来代替树中的空子树,其余节点叫做内部节点。增加了外部节点的二叉树被称为扩充二叉树.令s(x)为从节点x到它的子树的外部节点的所有路径中最短的一条,根据s(x)的定义可知,若x是外部节点,则s的值为0,若x为内部节点,则它的s值是:mins(L),s(R)+1其中L与R分别为x的左右孩子。定义高度优先左高树当且仅当一棵二叉树的任何一个内部节点,其左孩子的s值大于等于右孩子的s值时,该二叉树为高度优先左高树(height-biasedleftisttree,HBLT)。,左高树,2020/5/26,17,DataMining:ConceptsandTechniques,4左高树,左高树,2020/5/26,18,DataMining:ConceptsandTechniques,4左高树,定义最大HBLT即同时又是最大树的HBLT。定义最小HBLT即同时又是最小树的HBLT。定义重量优先左高树当且仅当一棵二叉树的任何一个内部节点,其左孩子的w值大于等于右孩子的w值时,该二叉树为重量优先左高树(weight-biasedleftisttree,WBLT)。定义最大(小)WBLT即同时又是最大(小)树的WBLT。,左高树,2020/5/26,19,DataMining:ConceptsandTechniques,4左高树,合并策略:令A、B为需要合并的两棵最大HBLT,如果其中一个为空,则将另一个作为合并的结果,因此可以假设两者均不为空。为实现合并,先比较两个根元素,较大者作为合并后的HBLT的根。假定A具有较大的根,且其左子树为L,C是由A的右子树与B合并而成的HBLT。A与B合并所得结果即是以A的根为根,L与C为左右子树的最大HBLT。如果L的s值小于C的s值,则C为左子树,否则L为左子树。,左高树,2020/5/26,20,DataMining:ConceptsandTechniques,4左高树,左高树,2020/5/26,21,DataMining:ConceptsandTechniques,4左高树,左高树,2020/5/26,22,DataMining:ConceptsandTechniques,4左高树,初始化最大HBLT首先创建n个最大HBLT,每个树中仅包含n个元素中的某一个,这n棵树排成一个FIFO队列,然后从队列中依次删除两个HBLT,将其合并,然后再加入队列末尾,直到最后只有一棵HBLT。,左高树,2020/5/26,23,DataMining:ConceptsandTechniques,4左高树,构造具有五个元素:7,1,9,11,2的一棵最大HBLT。为此,首先构造五个单元素的最大HBLT,并形成一个FIFO队列。把最前面的两个最大HBLT7和1从队列中删除并进行合并,所得结果如图a所示,将该结果加入到队列中。接下来从队列中删除两棵最大HBLT9和11并进行合并,所得结果如图b所示,也将该结果加入队列中。现在继续从队列中删除最大HBLT2及图a所得到的HBLT,并进行合并,所得结果如图c所示加入队列。下一对从队列中删除的最大HBLT如图b与c所示,经合并得到的最大HBLT如图d所示,将该结果插入到队列中。至此,队列中只有一棵最大HBLT,初始化工作完成。,左高树,2020/5/26,24,DataMining:ConceptsandTechniques,4左高树,HBLT的节点类templateclassHBLTNodefriendMaxHBLT;public:HBLTNode(constT,左高树,2020/5/26,25,DataMining:ConceptsandTechniques,4左高树,MaxHBLT类templateclassMaxHBLTpublic:MaxHBLT()root=0;MaxHBLT()Free(root);TMax()if(!root)throwOutOfBounds();returnroot-data;MaxHBLT,左高树,2020/5/26,26,DataMining:ConceptsandTechniques,4左高树,合并两棵左高树templatevoidMaxHBLT:Meld(HBLTNode*,左高树,2020/5/26,27,DataMining: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/5/26,28,DataMining:ConceptsandTechniques,4左高树,最大HBLT的插入templateMaxHBLT,左高树,2020/5/26,29,DataMining:ConceptsandTechniques,5应用1-堆排序,先将要排序的n个元素初始化为一个最大堆,然后每次从堆中提取(即删除)元素。各元素将按递减次序排列。templatevoidHeapSort(Ta,intn)/利用堆排序算法对a1:n进行排序/创建一个最大堆MaxHeapH(1);H.Initialize(a,n,n);/从最大堆中逐个抽取元素Tx;for(inti=n-1;i=1;i-)H.DeleteMax(x);ai+1=x;/在堆的析构函数中保存数组aH.Deactivate();,堆排序,2020/5/26,30,DataMining:ConceptsandTechniques,5应用2-霍夫曼编码,主要用途是实现数据压缩。设给出一段报文:CASTCASTSATATATASA字符集合是C,A,S,T,各个字符出现的频度(次数)是W2,7,4,5。若给每个字符以等长编码A:00T:10C:01S:11则总编码长度为(2+7+4+5)*2=36.若按各个字符出现的概率不同而给予不等长编码,可望减少总编码长度。因各字符出现的概率为2/18,7/18,4/18,5/18。,霍夫曼编码,2020/5/26,31,DataMining:ConceptsandTechniques,5应用2-霍夫曼编码,霍夫曼树中左分支赋0,右分支赋1,得霍夫曼编码(变长编码)。A:0T:10C:110S:111它的总编码长度:7*1+5*2+(2+4)*3=35。比等长编码的情形要短。总编码长度正好等于霍夫曼树的带权路径长度WPL。霍夫曼编码是一种无前缀编码。解码时不会混淆。,霍夫曼编码,2020/5/26,32,DataMining:ConceptsandTechniques,5应用2-霍夫曼编码,带权路径长度(WeightedPathLength,WPL)树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。霍夫曼树带权路径长度达到最小的扩充二叉树即为霍夫曼树。在霍夫曼树中,权值大的结点离根最近。,霍夫曼编码,2020/5/26,33,DataMining:ConceptsandTechniques,5应用2-霍夫曼编码,霍夫曼算法(1)由给定的n个权值w0,w1,w2,wn-1,构造具有n棵扩充二叉树的森林F=T0,T1,T2,Tn-1,其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点,其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止:在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删去这两棵二叉树。把新的二叉树加入F。,霍夫曼编码,2020/5/26,34,DataMining:ConceptsandTechniques,5应用2-霍夫曼编码,霍夫曼编码,2020/5/26,35,DataMining:ConceptsandTechniques,5应用2-霍夫曼编码,建立霍夫曼树templateBinaryTreeHuffmanTree(Ta,intn)/根据权重a1:n构造霍夫曼树/创建一个单节点树的数组Huffman*w=newHuffmann+1;BinaryTreez,zero;for(inti=1;iH(1);H.Initialize(w,n,n);/将堆中的树不断合并Huffmanx,y;for(i=1;in;i+)H.DeleteMin(x);H.DeleteMin(y);z.MakeTree(0,x.tree,y.tree);x.weight+=y.weight;x.tree=z;H.Insert(x);H.DeleteMin(x);/最后的树H.Deactivate();deletew;returnx.tree;,霍夫曼编码,2020/5/26,37,DataMining:ConceptsandTechniques,5应用3-机器调度,考察一个机械厂,其中有m台一模一样的机器。现有n个作业需要处理,设作业i的处理时间为ti,这个时间为从将作业放入机器直到从机器上取下作业的时间。所谓调度是指按作业在机器上的运行时间对作业进行分配,使得:一台机器在同一时间内只能处理一个作业。一个作业不能同时在两台机器上处理。作业i一旦运行,则需要ti个时间单位。,机器调度,2020/5/26,38,DataMining:ConceptsandTechniques,5应用3-机器调度,七个作业在三台机器上进行调度的情形,七个作业所需时间分别为(2,14,4,16,6,5,3)。三台机器分别被编号为M1、M2和M3。完成时间或调度长度为17,机器调度,2020/5/26,39,DataMining:ConceptsandTechniques,5应用3-机器调度,Task:确定如何进行调度才能使在m台机器上执行给定的n个作业时所需要的处理时间最短.调度问题是著名的NP-复杂问题中的一种。采用一个称为最长处理时间优先(longestprocessingtimefirst,LPT)的简单调度策略,在LPT算法中,作业按它们所需处理时间的递减顺序排列。在分配一个
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2022年2月马鞍山市直机关遴选公务员面试真题附带题目详解
- 2012自考试题及答案
- 2025年皖北煤电集团总医院招聘24人笔试备考题库及答案详解一套
- 学校入部申请书
- 《管理学》试题及答案
- 2025年民间借款合同范本
- 2025财务人员劳动合同范本(标准版)
- 2025年安徽省滁州市定远县中考三模语文试题
- 2025瑞雪红枫彩钢板合同李明锋
- 农民信息化技术培训服务合同
- 2023年山东省夏季普通高中学业水平合格考试会考生物试题及参考答案
- 四川省泸州市2024年中考物理试题(含答案)
- 第13课 立足专业 谋划发展 第一框
- 2024届浙江省台州市天台县英语八年级第二学期期末达标检测模拟试题含答案
- 银行保安服务 投标方案(技术标)
- 工学云周报范文200字
- 广东省湛江市2023-2024学年高一下学期期末调研考试语文试题及答案解析
- 国开(河北)2024年《法律工作者职业道德》形考任务1-4答案
- 山东省济南市高新区2023-2024学年八年级下学期期末物理试题
- 2024年遂宁市中考理科综合真题试卷(含答案解析)
- 2024年河北省中考道德与法治真题含解析
评论
0/150
提交评论