下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 优先队列及其应用

优先队列及其应用.doc

优先队列及其应用

骑牛撞交警宝贝
2017-10-25 0人阅读 举报 0 0 暂无简介

简介:本文档为《优先队列及其应用doc》,可适用于综合领域

优先队列及其应用雅礼朱全民优先队列的基本概念优先队列的基本概念队列:队列:FIFOFIFO(按元素进入队列的次序)(按元素进入队列的次序)优先队列(优先队列(PriorityQueuePriorityQueue):出队列的顺序由元):出队列的顺序由元素的优先级决定如:素的优先级决定如:医院中的急诊处理医院中的急诊处理操作系统中使用优先队列进行作业调度操作系统中使用优先队列进行作业调度事件驱动模拟处理。事件驱动模拟处理。优先队列的基本操作优先队列的基本操作ADTADTMaxPriorityQueueMaxPriorityQueue{{实例实例有限的元素集合每个元素都有一个优先权操作有限的元素集合每个元素都有一个优先权操作Create()Create():创建一个空的优先队列:创建一个空的优先队列Size()Size():返回队列中的元素数目:返回队列中的元素数目Max()Max():返回具有最大优先权的元素:返回具有最大优先权的元素Insert(x)Insert(x):将:将xx插入队列插入队列DeleteMaxDeleteMax(x)(x):从队列中给删除具有最大优先权的元素:从队列中给删除具有最大优先权的元素并将该元素返回至并将该元素返回至xx}}假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的但每个用户所需要服务时间都不同。为获得最大利润假设只要有用户机器就不会空闲我们可以把等待使用该机器的用户组织成一个最小优先队列优先权即为用户所需服务时间。当一个新的用户需要使用机器时将他她的请求加入优先队列。一旦机器可用则为需要最少服务时间(即具有最高优先权)的用户提供服务。如果每个用户所需时间相同但用户愿意支付的费用不同则可以用支付费用作为优先权一旦机器可用所交费用最多的用户可最先得到服务这时就要选择最大优先队列。对其事件队列所执行的操作)查找最小完成时间的机器)改变机器的完成时间构造构造一个最小优先队列队列中的元素即为机器元素的优先权为该机器的完成时间。当机器可用选择优先级最大的任务执行任务队列操作:)新任务到达插入最大优先队列)一旦机器可以开始运行一个新任务将具有最大优先权的任务从该机器的队列中删除并开始执行它。优先队列的线性表实现优先队列的线性表实现优先队列的另一种实现方式优先队列的另一种实现方式堆(堆(HeapHeap)。)。无序顺序表无序顺序表插入在表的末尾插入在表的末尾ΘΘ()()删除时先查找优先权最大的元素删除时先查找优先权最大的元素ΘΘ(n)(n)。。无序链表无序链表插入在链头插入在链头ΘΘ()()删除时先查找优先权最大的元素删除时先查找优先权最大的元素ΘΘ(n)(n)。。有序线性表有序线性表插入时间插入时间ΘΘ(n)(n)删除时间删除时间ΘΘ()()。。一个基本问题写一种数据结构完成以下种操作:(操作的总次数不超过)、插入一个数、询问最小值、删除最小值要求是这种操作都要快。。。输入输出输入每行一次操作有如下三种:x:表示插入X这个数:表示询问当前最小值:表示删除最小值输出对于每个询问最小值操作输出一行每行仅一个数表示当前的最小值。样例输入:次操作输出:用线性表作为数据结构无序表:–插入操作O()–询问最小值O(n)–删除最小值O(n)有序表:–插入操作O(n)–询问最小值O()–删除最小值O()堆的定义堆的定义如果将此数据元素序列用一维数组存储并将此数组对如果将此数据元素序列用一维数组存储并将此数组对应一棵完全二叉树则堆的含义可以理解为:在完全二叉应一棵完全二叉树则堆的含义可以理解为:在完全二叉树中任何非终端节点的值均不大于(或小于)其左、右孩树中任何非终端节点的值均不大于(或小于)其左、右孩子节点的值。子节点的值。设有设有nn个数据元素的值为(个数据元素的值为(kk,k,k,…,,…,kknn)如果它们满足)如果它们满足以下的关系:以下的关系:kkiikkii且且kkiikkii(或(或kkiikkii且且kkiikkii))((ii=,…,n=,…,n)则称之为堆()则称之为堆(HeapHeap)。)。堆(堆(HeapHeap))最小堆(最小堆(MinHeapMinHeap))最大堆(最大堆(MaxHeapMaxHeap))最小(大)堆最小(大)堆:位于:位于堆顶堆顶(即完全二叉树的根节点位(即完全二叉树的根节点位置)的节点的值是整个序列中最小(大)的。置)的节点的值是整个序列中最小(大)的。kkiikkii且且kkiikkiikkiikkii且且kkiikkii在堆中插入元素x首先将元素x放到堆中的最后一个位置(即最底层最右边的位置)然后不断地把x往上调整直到x调不动为止(即大于它现在的父亲或者x处于根结点)。定义一个堆:Varst:arraymaxnoflongint存储堆n:longint堆中元素个数()将新节点插到最后()把新节点和父亲进行交换()继续交换直到重新满足堆的性质插入(实际上是不断向上调整的过程)PROCup(k:longint){把第k个结点上调}beginwhilek>dobegini:=kdiv{i是k的父亲}ifsti>stkthenbeginswap(i,k)k:=i{交换结点i和k}endelseexitendend在堆中删除任意一个元素这里说指的删除任意一个元素是指在当前堆中位置为w的元素。过程如下:首先把位置w的元素和最后一个位置的元素交换然后删去最后一个位置这样w上的元素就被删除了。接着把位置w上的新元素不断下调直到满足堆的性质。()当前要删除的节点是根节点的左儿子()将根节点的左儿子和最后一个节点交换()将新的节点不断下调直到满足堆的性质删除(实际上是不断向下调整的过程)PROCdown(k:longint){把第k个结点往下调}beginwhilekk=),要求一个具有m个外部节点的扩充二叉树每个外部ki节点有一个wi与之对应作为它的权,使得带权外部路径长度最小其中li是从根到外部节点的路径长度。miiilw算法构造m个只有个节点的树找两个最小的权以这两个节点为左右儿子构造一个二叉树并将该数的根节点权之为左右儿子权值之和继续第二步直到剩下一棵树为止有n个任务每个任务有一个截止完成的时间Ti和完成需要的时间Ci。现在你一个人希望从时刻开始完成尽量多的任务。问最多能完成多少任务,分析首先不妨将任务按照截止时间排序。这时候我们可以采用贪心方法尽量选截止时间比较晚同时需要时间比较少的任务完成是最好的。于是得出一个结论:假设最优方案的组成的任务集合是U。如果存在一个不属于U的任务j对于某个属于,的满足Tj>Ti而且,jCi那么根据定理将K,i替换后肯定更优。于是得到了一个算法的基本流程:将任务按照Ti排序。从小到大枚举i。维护当前最优方案的集合U。每次将当前的任务I加入U后。如果不满足条件了那么删去U中耗时最长的任务。输出最优方案即可。因此我们需要使用一种数据结构它能快速删除耗时最长的任务同时快速的插入一个新元素。显然使用大根堆即能满足题目要求。juiceJonh正在研制一种有趣的―水杯‖:)底面是WxH的相同小方格组成如果分开计算f(i):–对于第一类:f(i)=min{f(j)A(j)j}i–对于第二类:f(i)=min{f(j)A(j)j}i分析()我们将两类决策分开计算。随着i的增加会有一些决策从第一类转到第二类。我们用两个二叉堆维护两类决策用对于第一类决策用f(j)A(j)j作为关键字第二类决策用f(j)A(j)j作为关键字。二叉堆可以进行的操作有:插入元素、删除元素、取最值。分析()两个特殊处理:–预处理:计算每个决策在什么时候从第一类转到第二类–记录每个决策在堆中的位置这样查找的时间复杂度就是O()优化后的时间复杂度为O(nlogn)思考:还有没有更好的算法,

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/15

优先队列及其应用

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利