内蒙古大学《算法与数据结构》讲义09优先队列
27页1、下载第9章优 先 队 列与第6章F I F O结构的队列不同,优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序,而不是元素进入队列的次序。可以利用堆数据结构来高效地实现优先队列。堆是一棵完全二叉树,可用 8 . 4节所介绍的公式化描述方法来高效存储完全二叉树。在高度和重量上取得平衡的左高树很适合于用来实现优先队列。本章的内容涵盖了堆和左高树。在本章的应用部分,利用堆开发了一种复杂性为O (nl o gn) 的排序算法,称为堆排序。在第2章所介绍的对n 个元素进行排序的算法,其复杂性均为O (n2 )。虽然第3章介绍的箱子排序和基数排序算法的运行时间为(n),但算法中元素的取值必须在合适的范围内。堆排序是迄今为止所讨论的第一种复杂性优于O (n2 ) 的通用排序算法,第1 4章将讨论另一种与堆排序具有相同复杂性的排序算法。从渐进复杂性的观点来看,堆排序是一种优化的排序算法,因为可以证明,任何通用的排序算法都是通过成对比较元素来获得 (nl o gn) 复杂性的(见1 4 . 4 . 2节) 。本节所考察的另外两个应用是机器调度和生成霍夫曼编码。机
2、器调度问题属于 N P -复杂问题,对于这类问题不存在具有多项式时间复杂性的算法。而第 2章提到的大量事实表明,只有具有多项式时间复杂性的算法才是可行的,因此,经常利用近似算法或启发式算法来解决 N P -完全问题,这些算法能在合理的时间内完成,但并不能保证找到最佳结果。对于机器调度应用,利用堆数据结构获得了有效解决机器调度问题的近似算法。本章没有提供有关左高树的应用,其实6 . 4 . 4节中的工厂仿真在这方面是一个很好的应用。9.1 引言优先队列(priority queue)是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除。在最小优先队列(min priorityq u e u e)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue) ,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素。优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行。最大优先权队列的抽象数据类型描述如 ADT 9-1所示,最小优先队列的抽象数据类
3、型描述与之类似,只需将最大改为最小即可。ADT 9-1 最大优先队列的抽象数据类型描述抽象数据类型M a x P r i o r i t y Q u e u e实例有限的元素集合,每个元素都有一个优先权操作C reate ( ):创建一个空的优先队列Size ( ):返回队列中的元素数目Max ( ):返回具有最大优先权的元素I n s e rt (x):将x 插入队列DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至 x例9-1 假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的,但每个用户所需要服务时间都不同。为获得最大利润,假设只要有用户机器就不会空闲,我们可以把等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需服务时间。当一个新的用户需要使用机器时,将他 /她的请求加入优先队列。一旦机器可用,则为需要最少服务时间(即具有最高优先权)的用户提供服务。如果每个用户所需时间相同,但用户愿意支付的费用不同,则可以用支付费用作为优先权,一旦机器可用,所交费用最多的用户可最先得到服务,这时就要选择最大优先队列。例9-2 考察6 . 4
4、 . 4节所介绍的工厂仿真问题,对其事件队列所执行的操作有:1)查找具有最小完成时间的机器;2)改变该机器的完成时间。假设我们构造一个最小优先队列,队列中的元素即为机器,元素的优先权为该机器的完成时间。最小优先队列的查找操作可用来返回具有最小完成时间的机器。为了修改此机器的完成时间,可以先从队列中删除具有最小优先权的元素,然后用新的完成时间作为该元素的优先权并将其插入队列。实际上,为了满足事件表的应用,可以在最小优先队列的A D T表中新增加一个操作,用来修改具有最小优先权元素的优先权。最大优先队列也可用于工厂仿真问题。在6 . 4 . 4节中的仿真程序中,每台机器按先进先出的方式来完成等待服务的任务,因此可以为每台机器配置了一个 F I F O队列。但如果将服务规则改为“一旦机器可用,则从等待任务中选择优先权最大的任务进行处理” ,每台机器就需要一个最大优先队列。每台机器执行的操作有: 1)每当一个新任务到达,将其插入该机器的最大优先队列中;2)一旦机器可以开始运行一个新任务,将具有最大优先权的任务从该机器的队列中删除,并开始执行它。当每个机器的服务规则如上述改变之后,则需用一个最小
5、优先队列来表示仿真问题中的事件表,用一个最大优先队列来存储每台机器旁的等待任务。在 6 . 4 . 4节的仿真模型中我们事先已经知道事件表的长度,即机器的台数,并且在整个仿真过程中事件表的长度不会改变,所以可采用一个公式化描述的优先权队列来表示时间表。但更常见的是必须考虑加入新机器或移走旧机器的情况,所以最好使用链表描述的优先队列,这样在队列建立时就不必事先预测队列的最大长度,也不必动态地改变数组的大小。如同在6 . 4 . 4节中选择链表F I F O队列而不是公式化队列一样,每个机器的优先权队列也最好是链表队列。每个机器的队列长度在仿真过程中不断变化,而所有队列的长度之和却总是等于未完成的任务数之和。本章提供了优先权队列有效的描述方法。鉴于最大优先队列与最小优先队列十分类似,故在此只明确给出了最大优先队列的描述。9.2 线性表描述最大优先队列最简单的方法是采用无序线性表。假设有一个具有n 个元素的优先队列,如果利用公式(2 - 1) ,那么插入操作可以十分容易地在表的右端末尾执行,插入所需时间为( 1 )。删除操作时必须查找优先权最大的元素,即在未排序的n 个元素中查找具有最大优先
《内蒙古大学《算法与数据结构》讲义09优先队列》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义09优先队列》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页