数据结构算法与应用-c++语言描述009new

《数据结构算法与应用-c++语言描述009new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下载下载第9章优先队列与第6章FIFO结构的队列不同，优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序。可以利用堆数据结构来高效地实现优先队列。堆是一棵完全二叉树，可用8.4节所介绍的公式化描述方法来高效存储完全二叉树。在高度和重量上取得平衡的左高树很适合于用来实现优先队列。本章的内容涵盖了堆和左高树。在本章的应用部分，利用堆开发了一种复杂性为O(nlogn)的排序算法，称为堆排序。在第22章所介绍的对n个元素进行排序的算法，其复杂性均为O(n)。虽然第3章介绍的箱子排序和基数排序算法的运行时间为(n)，但算法中元

2、素的取值必须在合适的范围内。堆排序是迄今为2止所讨论的第一种复杂性优于O(n)的通用排序算法，第14章将讨论另一种与堆排序具有相同复杂性的排序算法。从渐进复杂性的观点来看，堆排序是一种优化的排序算法，因为可以证明，任何通用的排序算法都是通过成对比较元素来获得W(nlogn)复杂性的（见14.4.2节）。本节所考察的另外两个应用是机器调度和生成霍夫曼编码。机器调度问题属于NP-复杂问题，对于这类问题不存在具有多项式时间复杂性的算法。而第2章提到的大量事实表明，只有具有多项式时间复杂性的算法才是可行的，因此，经常利用近似算法或启发式算法来解决NP-完全问题，这些算法能在合理的时间内完成

3、，但并不能保证找到最佳结果。对于机器调度应用，利用堆数据结构获得了有效解决机器调度问题的近似算法。本章没有提供有关左高树的应用，其实6.4.4节中的工厂仿真在这方面是一个很好的应用。9.1引言优先队列（priorityqueue）是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有1)查找；2)插入一个新元素；3)删除。在最小优先队列（minpriorityqueue）中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列（maxpriorityqueue），查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。优先权队列中的元素可

4、以有相同的优先权，查找与删除操作可根据任意优先权进行。最大优先权队列的抽象数据类型描述如ADT9-1所示，最小优先队列的抽象数据类型描述与之类似，只需将最大改为最小即可。ADT9-1最大优先队列的抽象数据类型描述抽象数据类型MaxPriorityQueue{实例有限的元素集合，每个元素都有一个优先权操作Create()：创建一个空的优先队列Size()：返回队列中的元素数目Max()：返回具有最大优先权的元素第9章优先队列277下载Insert(x)：将x插入队列DeleteMax(x)：从队列中删除具有最大优先权的元素，并将该元素返回至x}例9-1假设我们对机器服务进行收费。每个

5、用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。为获得最大利润，假设只要有用户机器就不会空闲，我们可以把等待使用该机器的用户组织成一个最小优先队列，优先权即为用户所需服务时间。当一个新的用户需要使用机器时，将他/她的请求加入优先队列。一旦机器可用，则为需要最少服务时间（即具有最高优先权）的用户提供服务。如果每个用户所需时间相同，但用户愿意支付的费用不同，则可以用支付费用作为优先权，一旦机器可用，所交费用最多的用户可最先得到服务，这时就要选择最大优先队列。例9-2考察6.4.4节所介绍的工厂仿真问题，对其事件队列所执行的操作有：1）查找具有最小完成时间的机器；2）

6、改变该机器的完成时间。假设我们构造一个最小优先队列，队列中的元素即为机器，元素的优先权为该机器的完成时间。最小优先队列的查找操作可用来返回具有最小完成时间的机器。为了修改此机器的完成时间，可以先从队列中删除具有最小优先权的元素，然后用新的完成时间作为该元素的优先权并将其插入队列。实际上，为了满足事件表的应用，可以在最小优先队列的ADT表中新增加一个操作，用来修改具有最小优先权元素的优先权。最大优先队列也可用于工厂仿真问题。在6.4.4节中的仿真程序中，每台机器按先进先出的方式来完成等待服务的任务，因此可以为每台机器配置了一个FIFO队列。但如果将服务规则改为“一旦机器可用，则从等待

7、任务中选择优先权最大的任务进行处理”，每台机器就需要一个最大优先队列。每台机器执行的操作有：1）每当一个新任务到达，将其插入该机器的最大优先队列中；2）一旦机器可以开始运行一个新任务，将具有最大优先权的任务从该机器的队列中删除，并开始执行它。当每个机器的服务规则如上述改变之后，则需用一个最小优先队列来表示仿真问题中的事件表，用一个最大优先队列来存储每台机器旁的等待任务。在6.4.4节的仿真模型中我们事先已经知道事件表的长度，即机器的台数，并且在整个仿真过程中事件表的长