《优先队列及其应用》.ppt

该【《优先队列及其应用》 】是由【相惜】上传分享，文档一共【87】页，该文档可以免费在线阅读，需要了解更多关于【《优先队列及其应用》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。优先队列及其应用雅礼朱全民编辑课件优先队列的根本概念队列:FIFO〔按元素进入队列的次序〕;优先队列〔PriorityQueue〕:出队列的顺序由元素的优先级决定,如:医院中的急诊处理;操作系统中使用优先队列进行作业调度;事件驱动模拟处理。编辑课件优先队列的根本操作ADTMaxPriorityQueue{实例有限的元素集合,每个元素都有一个优先权操作Create():创立一个空的优先队列Size():返回队列中的元素数目Max():返回具有最大优先权的元素Insert(x):将x插入队列DeleteMax(x):从队列中给删除具有最大优先权的元素,并将该元素返回至x}编辑课件假设我们对机器效劳进行收费。每个用户每次使用机器所付费用都是相同的,但每个用户所需要效劳时间都不同。为获得最大利润,假设只要有用户机器就不会空闲,我们可以把等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需效劳时间。当一个新的用户需要使用机器时,将他/她的请求参加优先队列。一旦机器可用,那么为需要最少效劳时间〔即具有最高优先权〕的用户提供效劳。如果每个用户所需时间相同,但用户愿意支付的费用不同,那么可以用支付费用作为优先权,一旦机器可用,所交费用最多的用户可最先得到效劳,这时就要选择最大优先队列。引例1:机器效劳收费编辑课件引例2工厂仿真对其事件队列所执行的操作查找最小完成时间的机器改变机器的完成时间构造构造一个最小优先队列,队列中的元素即为机器,元素的优先权为该机器的完成时间。当机器可用,选择优先级最大的任务执行,任务队列操作:新任务到达,插入最大优先队列一旦机器可以开始运行一个新任务,将具有最大优先权的任务从该机器的队列中删除,并开始执行它。编辑课件优先队列的线性表实现优先队列的另一种实现方式——堆〔Heap〕。无序顺序表插入在表的末尾,Θ(1)删除时先查找优先权最大的元素,Θ(n)。无序链表插入在链头,Θ(1)删除时先查找优先权最大的元素,Θ(n)。有序线性表插入时间,Θ(n)删除时间,Θ(1)。编辑课件一个根本问题写一种数据结构,完成以下3种操作:(操作的总次数不超过100000)1、插入一个数2、询问最小值3、删除最小值要求是这3种操作都要快。。。编辑课件输入输出输入 每行一次操作,有如下三种: 1x:表示插入X这个数 2:表示询问当前最小值 3:表示删除最小值输出 对于每个询问最小值操作,输出一行,每行仅一个数,表示当前的最小值。编辑课件样例输入:9-----9次操作1202**********输出:20102030编辑课件用线性表作为数据结构无序表:插入操作O〔1〕询问最小值O〔n〕删除最小值O〔n〕有序表:插入操作O〔n〕询问最小值O〔1〕删除最小值O〔1〕编辑课件