优先队列及其应用.ppt

《优先队列及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、优先队列及其应用雅礼朱全民优先队列的基本概念队列：FIFO（按元素进入队列的次序）；优先队列（PriorityQueue）：出队列的顺序由元素的优先级决定，如：医院中的急诊处理；操作系统中使用优先队列进行作业调度；事件驱动模拟处理。优先队列的基本操作ADTMaxPriorityQueue{实例有限的元素集合，每个元素都有一个优先权操作Create()：创建一个空的优先队列Size()：返回队列中的元素数目Max()：返回具有最大优先权的元素Insert(x)：将x插入队列DeleteMax(x)：从

2、队列中给删除具有最大优先权的元素，并将该元素返回至x}假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。为获得最大利润，假设只要有用户机器就不会空闲，我们可以把等待使用该机器的用户组织成一个最小优先队列，优先权即为用户所需服务时间。当一个新的用户需要使用机器时，将他/她的请求加入优先队列。一旦机器可用，则为需要最少服务时间（即具有最高优先权）的用户提供服务。如果每个用户所需时间相同，但用户愿意支付的费用不同，则可以用支付费用作为优先权，一旦机器可用，

3、所交费用最多的用户可最先得到服务，这时就要选择最大优先队列。引例1：机器服务收费引例2工厂仿真对其事件队列所执行的操作查找最小完成时间的机器改变机器的完成时间构造构造一个最小优先队列，队列中的元素即为机器，元素的优先权为该机器的完成时间。当机器可用，选择优先级最大的任务执行，任务队列操作：新任务到达，插入最大优先队列一旦机器可以开始运行一个新任务，将具有最大优先权的任务从该机器的队列中删除，并开始执行它。优先队列的线性表实现优先队列的另一种实现方式——堆（Heap）。无序顺序表插入在表的末尾，Θ(1

4、)删除时先查找优先权最大的元素，Θ(n)。无序链表插入在链头，Θ(1)删除时先查找优先权最大的元素，Θ(n)。有序线性表插入时间，Θ(n)删除时间，Θ(1)。一个基本问题写一种数据结构，完成以下3种操作：(操作的总次数不超过100000)1、插入一个数2、询问最小值3、删除最小值要求是这3种操作都要快。。。输入输出输入每行一次操作，有如下三种：1x：表示插入X这个数2：表示询问当前最小值3：表示删除最小值输出对于每个询问最小值操作，输出一行，每行仅一个数，表示当前的最小值。样例输入：9-----9次

5、操作120213011023232输出：20102030用线性表作为数据结构无序表：插入操作O（1）询问最小值O（n）删除最小值O（n）有序表：插入操作O（n）询问最小值O（1）删除最小值O（1）堆的定义如果将此数据元素序列用一维数组存储，并将此数组对应一棵完全二叉树，则堆的含义可以理解为：在完全二叉树中任何非终端节点的值均不大于（或小于）其左、右孩子节点的值。设有n个数据元素的值为（k1,k2,…,kn），如果它们满足以下的关系：ki≤k2i且ki≤k2i+1（或ki≥k2i且ki≥k2i+1）（

6、i=1,…,n/2），则称之为堆（Heap）。堆（Heap）9172378876531534587784593153231765最小堆（MinHeap）最大堆（MaxHeap）9176523457887533187785345659311723最小（大）堆：位于堆顶（即完全二叉树的根节点位置）的节点的值是整个序列中最小（大）的。ki≤k2i且ki≤k2i+1ki≥k2i且ki≥k2i+1在堆中插入元素x首先将元素x放到堆中的最后一个位置（即最底层最右边的位置），然后不断地把x往上调整，直到x调不动为

7、止（即大于它现在的父亲，或者x处于根结点）。定义一个堆:Varst:array[1..maxn]oflongint;//存储堆n:longint;//堆中元素个数13545786213557864(1)将新节点插到最后(2)把新节点和父亲进行交换1557864(3)继续交换，直到重新满足堆的性质322插入(实际上是不断向上调整的过程)PROCup(k:longint);{把第k个结点上调}beginwhilek>1dobegini:=kdiv2;{i是k的父亲}ifst[i]>st[k]thenbe

8、ginswap(i,k);k:=i;{交换结点i和k}endelseexit;end;end;在堆中删除任意一个元素这里说指的删除任意一个元素，是指在当前堆中位置为w的元素。过程如下：首先把位置w的元素和最后一个位置的元素交换，然后删去最后一个位置，这样w上的元素就被删除了。接着把位置w上的新元素不断下调，直到满足堆的性质。155786431557864315578634(1)当前要删除的节点是根节点的左儿子(2)将根节点的左儿子和最后一个节点交换(3)将新的节点不断