Chapter9优先队列.ppt

1、Chapter9优先队列，中国地质大学信息工程学院，2020/6/5， 2，2，Chapter9优先队列，9.1优先队列的基本概念9.2堆9.3.1堆排序9.3.1霍夫曼代码，3，9.1优先队列的基本概念，队列： FIFO优先队列：离开队列的顺序是？ 在操作系统中使用优先队列调度作业的事件驱动的模拟过程，这是由诸如医院中的急救等因素的优先级决定的。 4，最大优先级队列的ADT，ADTMaxPriorityQueue实例有限元集合各元素中的优先级操作Create () :空优先级队列Size () :队列中的元素数Max () :优先级最大的元素Insert(x ) :在队列中插入x delete max :从队列中删除优先级最大的元素，并返回x，5，优先级队列的线性表实现，优先级队列的另一种实现方法堆(Heap )。 无序顺序表插入表的末尾，(1)被删除时，优先度最大的要素，(n )首先被检索。无秩序的链表被插入链头，在(1)被删除时，首先检索优先级最大的要素，(n )。 秩序线性表插入时间、(n )删除时间、(1)。 6、回顾特性将具有6n个节点的完全二叉树从上到下，同一层从左到右连续为节点编号1、2、n。 将这个完全二叉树中的一个要素的编号设为I，1n。 以下关系成立：(2)2in时，该元素没有左孩子。 否则，左边的孩子的号码是2i，(2i 1n的情况下，这个元素没有右边的孩子。 否则，右边孩子的号码是2i 1。 (1)如果i1，则节点I是根，而如果没有父母的i1，则节点I的父母节点号为具有特性5-n个节点的完全二叉树的深度h为。7，7，9.2.1堆的定义用一维数组存储该数据元素的序列，当使该数组与完全二叉树相对应时，可理解堆的意思是，在完全二叉树中，任何非终端节点的值都不比其左右的孩子节点的值大(或不小于)。 设置n个数据元素的值为(k1，k2，kn )，并且如果满足kik2I且kik2i1(或kik2I并且kik2i 1)(i=1，n/2 )的关系，则被称为堆(Heap )。9.2堆、8、最小堆、最大堆、最小堆(大)堆：位于堆顶部(即完全二叉树的根节点的位置)的节点值是整个序列中的最小(大)。 kik2i且kik2i 1、kik2i且kik2i 1、9、最大堆类MaxHeap的定义： Page281、templateclasssmaxheap public : max heap (intmax heapsize=) MaxHeap()deleteheap； intsize () const returncurrenttsize； bool isempty () returncurrentsize=0； returncurrentsize=maxsize； TMax ()堆栈顶部元素 if (current tsize=0) thrwoutfbounds ()； returnheap1； 10，MaxHeap，11，MaxHeap的构造函数，templatemaxheap :30 max heap (intmax heapsize ) /maxheapconstructor.maxsize=max heapsize heap=newTMaxSize 1； CurrentSize=0； 12，9.2.2最大堆的插入，例如在右堆中分别插入以下要素： (1)值为1； (2)值是5。(3)值是21。 1、13、(1)在已经建立的最大堆后插入数据元素(很有可能破坏堆的性质)。 (2)插入节点I后，比较节点I的值和其父节点i/2的值的大小，从下向上调整.在节点I的值大于其父节点i/2的值的情况下，交换两个节点，I指其父节点，i=1(i是根节点)或最大堆的插入算法思想，14，21，1、2、3、4、5、6、在最大堆中插入21、15，最大堆，templateMaxHeap，算法时间复杂度： O(log2n )，16，9.2.3删除最大堆，从最大堆中删除最大值的元素： (1)最大堆将堆栈的最后一个要素节点移动到堆栈顶部(3)从堆的当前要素数中减去1 (4)从炉顶向下重新调整到炉中。删除、值为21的节点，将最后一个元素嵌入堆上，示例、17、重新调整为堆，删除值为20的元素，将重新调整为堆上，10、15、18，删除最大堆，templateMaxHeap/childofi/是/noheap I =heap ci ； /movechildupi=ci； /movedownalevelci*=2； APS I =y； return*this； 算法时间复杂度： O(log2n )，ci指I左右孩子中值大的节点，复制20，9.2.4最大堆的初始化，数组，并调整它形成一个堆。 最后的分支节点一定是最后的叶节点的父母。 i=CurrentSize/2，例如21，22，23，24，25，最大堆初始化，templatevoidmaxheap :30 initialize (ta ，intsize，intarray size ) /in heap=a； CurrentSize=size； 最大尺寸=阵列尺寸； /makeintoamaxheap最后一个分支节点for(inti=CurrentSize/2； i=1； i-)Ty=heapi； /roottofubtree/findplacetoputyintc=2* I； /parentofcistargetposofy，26，最大堆初始化，while(c=heapc)break；/是/noheap c/2 =heap c ； /movechildupc*=2；/移动降级 c/2 =y； ，27，最大堆初始化函数的时间复杂性，for循环： for(inti=CurrentSize/2； i=1； I-)1次所花费的时间： O(logn )循环数： n/2的总时间复杂度： O(nlogn )，最佳情况下，时间复杂度(n )，即数组元素由最大堆组织。 28、while循环的每一次时间是O(hi )，hi是以I为根节点的子树的高度。 因为第j层最多包含2j-1个节点，所以最多2j-1个节点具有相同的高度hi=h-j 1，初始化算法时间的复杂性： O(nlogn )，基本的计算方法，29，另一个计算方法，对于n个节点的堆栈， 在制作与完全二叉树层数logn相对应的第I层上的节点数最大为2i(i0 )的堆栈的过程中，对每个非叶节点向下方调整，并且调整到最下层，因此第I层上的节点被向下方调整到最下层的次数，因此堆整体的时间为j=log 因此，堆算法的时间复杂度可以在O(n )线性时间中将无序序列转换为堆序列！30，放学后练习，Page285 :练习MinHeap练习9 :模仿在max heap中实现DeleteMax ()的算法的优化，31，9.3.1堆栈排序，(1)将排序的n个要素初始化为最大堆栈(2)每次中要素(3)各要素按降序排列，49，25，21，16，08，1，2，3，4，5，6，08，25，25，16，21，49，1，3，6，5，4，2，例子，9.3堆栈的应用： 21，16，49，1，2，3，4，5，6，16，25，08，25 21，49，1，3，6，5，4，2，25，* 16，08，21，25，49，1，2，3，25，25，25 、25、49、49、2、3、4、5、6、08 16、25 *、21、49、1、3、6、5、4、2、16、08、25、21、25、49、1、2、3、4、4 用堆叠排序算法对1，3，6，5，4，34，templatevoidHeapSort(Ta，intn)/a1:n进行排序MaxHeapH(1)； h .初始化(a，n，n) Tx； /从最大堆中一个个地提取要素for (inti=n-1； i=1； I- ) h .删除最大值(x )； ai 1=x； /堆的析构函数中数组aH.Deactivate ()； ，初始化所需的时间： O(nlogn )删除所需的时间： O(log2n )累积时间的复杂性： O(nlog2n )，35，补充：扩展二叉树，添加外部节点，代替树中的空树。36、外部节点代码原则、a :00 b :010 c 3360011 d 336011 e 336011 f :11，37，1、相关基本概念、(1)路径(Path ) :从一个节点到另一个节点的分支构成两个节点之间的路径(从节点a到节点h的路径长度： 3，二叉树的路径长度： PL=0 1 1 2 2 2 3 3=14，(4)节点的加权路径长度：从该节点到树根的路径长度与节点上的权重的积。 9.3.2霍夫曼编码，38，(5)二叉树的加权路径长度(WPL ) :树中所有叶节点的加权路径长度之和。假设二叉树拥有所有n个叶节点的权重，并且将wk设为第k个(k=1，2，n )叶节点的权重，则lk是第k个(k=1，2，3，n )叶节点的路径长度。 wpl=8*2*3*3*3*1*2=39，例如，39，例子以下两棵二叉树都有四个叶节点a、b、c、d，权重分别为7、5、2、4，各树的加权路径长度分别为：wpl=7*。 具有最小加权路径长度的二叉树也称为霍夫曼树，并假定wpl=7*1*5*2*3*3=35，具有n个权重值w1，w2，wn，构建具有n个叶节点的二叉树，并生成各叶节点的权重(1)哈夫曼树可能不唯一，但得到的WPL值全部相等，最小(2)满二叉树，完全二叉树不一定是霍夫曼树，(3)霍夫曼树的特性：越是权重大的叶节点，越靠近根，权重小的叶节点越远离根没有度为1的节点！ 因为41、结构权重的集合是w1，w2，wn霍夫曼树，所以提出了一种被称为霍夫曼算法的结构算法。 根据算法思想(1)给定的n个权重w1，w2，wn，构筑n个叶节点只有一个的二叉树，得到一个二叉树的集合F=T1，T2，Tn，在(2)f中选择根节点的权重最小和次小的二叉树作为左右的子树进行更新该新二叉树的根节点的权重，在作为其左右子根节点的权重之和的(3)集合f中删除作为左右子树的二叉树，把新作成的二叉树加到集合f上，重复(2)、(3)的顺序，直到(4)f中只剩下一棵二叉树为止，就作成了该树、2、哈夫曼算法、示范、42、构建过程的示例，构建给定权重w= 2，4，5，7，8 集合，霍夫曼树。 2，4，5，7，8，(1)F :(2)F :2，4，5，7，7，8，11，43，4 ) f :7，8，15，(5)F:26，霍夫曼树，44，霍夫曼树另外，在通信的情况下，将传输的字符变换为由二进制字符0，1构成的字符串，称为编码。 例如，将传输的电文设为“ABACCDA”。 等长编码：各字符的代码长度相同。 优点：解码容易缺点：电文代码长，传输效率低。 3、霍夫曼编码，上述电文为0001001011100，接收者可以用两位一点解码。 A:00； b:01 c:10 d:11，45，例如，将上述电文 ABACCDA 中文字代码设计为A:0的B:00 C:1； D:01为电文： 000011010，产生多义性，例如： 0000可以解释为AAAA、ABA、BB等。 为了设计不同长度的代码，任何字符的代码都必须不是其他字符的代码的前缀，此代码称为前缀代码。 如果考虑将电文中出现次数多的文字尽可能短的代码，传输电文的全长就会减少。不等长度编码，46，利用二叉树进行前缀编码，0、1、0、0、1、1，前缀编码示例，约定：左分支表示字符“0”，右分支表示字符“1”，将由从根节点到叶节点的路径分支上的字符构成的字符串作为该叶节点的代码。 这样得到的一定是二进制前缀代码。 47、如何得到电文全长最短的二进制代码？ 如果各文字在电文中出现的次数为wi，其代码长度为li，电文中有n个文字的话，电文的总长对应于：二叉树，如果将wi作为叶节点的权利，则li为从根到叶的路径长，正好为二叉树的加权路径长。 设计电文全长最短的二进制前缀码，是一个以n种字符出现频率创造权利、设计哈夫曼树的问