《堆结构及其应用》PPT课件.ppt

常州市第一中学 林厚从,堆结构及其应用,一、堆结构 堆结构是一种数组对象，它可以被视为一棵完全二叉树，树中每个结点与数组中存放该结点中值的那个元素相对应，如下图：,左边的图（a）是一棵典型的完全二叉树，结点上方为编号，结点的值在圆圈当中。右边的图(b)是我们非常熟悉的一维数组，当又不是一般意义上的数组，因为这个数组存储了左边的二叉树结构。,常州市第一中学 林厚从,堆结构及其应用,表示一个堆的数组具有以下一些属性：设数组A的长度为len，二叉树的结点个数为size，sizelen，则Ai存储二叉树中编号为i的结点值（1isize），而Asize以后的元素并不属于相应的堆，树的根为A1，并且利用完全二叉树的性质，我们很容易求第i个结点的父结点（parent(i)）、左孩子结点(left(i)、右孩子结点(right(i)的下标了,分别为：trunc(i/2)、2i、2i+1；,更重要的是，堆具有这样一个性质，对除根以外的每个结点i，Aparent(i)Ai。即除根结点以外，所有结点的值都不得超过其父结点的值，这样就推出，堆中的最大元素存放在根结点中，且每一结点的子树中的结点值都小于等于该结点的值，这种堆又称为“大根堆”；反之，对除根以外的每个结点i，Aparent(i)Ai的堆，称为“小根堆”。,常州市第一中学 林厚从,堆结构及其应用,例1、合并果子（NOIP2004高中组第2题） 【问题描述】fruit.?(pas,c,c+) 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。,常州市第一中学 林厚从,堆结构及其应用,【输入文件】 输入文件fruit.in包括两行，第一行是一个整数n（1 = n = 30000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 = ai = 20000）是第i种果子的数目。 【输出文件】 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。 【样例输入】 3 1 2 9 【样例输出】 15 【数据规模】 对于30%的数据，保证有n = 1000； 对于50%的数据，保证有n = 5000； 对于全部的数据，保证有n = 30000。,【说明】 比赛中临时改成保证所有n = 10000。每个点测试时限均为1秒，测试机器为P4/2.8/512MB。,常州市第一中学 林厚从,堆结构及其应用,【问题分析】 1、算法分析 将这个问题换一个角度描述：给定n个叶结点，每个结点有一个权值Wi，将它们中两个、两个合并为树，假设每个结点从根到它的距离是Di，我们的目标就是使得最终的(wi * di)最小。 于是，这个问题就变为了经典的Huffman树问题。Huffman树的构造方法如下： (1) 从森林里取两个权和最小的结点； (2) 将它们的权和相加，得到新的结点，并且把原结点删除，将新结点插入到森林中； (3) 重复(1)(2)，直到整个森林里只有一棵树。,常州市第一中学 林厚从,堆结构及其应用,2、数据结构 很显然，问题当中需要执行的操作是：(1) 从一个表中取出最小的数; (2) 插入一个数字到这个表中。如果用一般的一维数组去操作，则时间复杂度为O（n*n），现在会超时。实际上支持动态查找最小数和动态插入操作的数据结构，我们可以选择用堆来实现。因为取的是最小元素，所以我们要用小根堆实现。 用堆的关键部分是两个操作：put操作，即往堆中加入一个元素； get操作，即从堆中取出并删除一个元素。,* 往堆中加入一个元素的算法(put)如下： 1、在堆尾加入一个元素，并把这个结点置为当前结点。 2、比较当前结点和它父结点的大小 如果当前结点小于父结点，则交换它们的值，并把父结点置为当前结 点,转2;如果当前结点大于等于父结点，则转3。 3、结束。,重复n次put操作，即可建立一个小根堆。,常州市第一中学 林厚从,堆结构及其应用,样例太简单，我们再举一个例子看看具体过程： 设n=10，10堆果子的数量分别为：3 5 1 7 6 4 2 5 4 1。,设一个堆结构heap110,现在先考虑同put操作建一个小根堆，具体方法是每次读入一个数插入到堆尾，再通过调整使得满足堆的性质(从堆尾son=len开始，判断它与父结点son div 2的大小，若heapson=heapson div 2为止)。开始时堆的长度len=0。,常州市第一中学 林厚从,堆结构及其应用,常州市第一中学 林厚从,堆结构及其应用,常州市第一中学 林厚从,堆结构及其应用,实际上，我们也可以直接用完全二叉树的形式描述出这个过程，得到如下的一棵完全二叉树（堆）：,常州市第一中学 林厚从,堆结构及其应用,* 从堆中取出并删除一个元素的算法(get)如下： 1、取出堆的根结点的值。 2、把堆的最后一个结点（len）放到根的位置上，把根覆盖掉。把堆的长度减一。 3、把根结点置为当前父结点fa。 4、如果fa无儿子（falen div 2），则转6；否则，把fa的两（或一）个儿子中值最小的那个置为当前的子结点son。 5、比较fa与son的值， 如果fa的值小于或等于son，则转6；否则，交换这两个结点的值，把fa指向son，转4。 6、结束。 如上图，len=10，第1次get操作，得到1，把heaplen赋值给heap1，len:=len-1，再调整heap1heaplen，使得满足堆的性质。 结果如下：,常州市第一中学 林厚从,堆结构及其应用,常州市第一中学 林厚从,堆结构及其应用,整个程序开始时通过n次get操作建立一个小根堆，然后不断重复如下操作：两次get操作取出两个最小数累加起来，并且形成一个新的结点，再插入到堆中。如1+1=2，再把2插入到堆的后面一个位置，然后从下往上调整，使得包括2在内的数组满足堆的性质，即：,get和put操作的复杂度均为log2n。所以建堆复杂度为nlog2n。合并果子时，每次需要从堆中取出两个数，然后再加入一个数，因此一次合并的复杂度为3log2n，共n-1次。所以整道题目的复杂度是nlog2n。,常州市第一中学 林厚从,堆结构及其应用,program fruit; const maxn=30000; var heap:array1maxn of longint; ans,n,len,a,b,i,tmp:longint; procedure put(x:longint); var fa,son,tmp:longint; begin len:=len+1; heaplen:=x; son:=len; while (son1)and(heapson div 2heapson) do begin tmp:=heapson div 2; heapson div 2:=heapson; heapson:=tmp; son:=son div 2; end; end;,常州市第一中学 林厚从,堆结构及其应用,function get:longint; var fa,son,tmp:longint; stop:boolean; begin get:=heap1;heap1:=heaplen;len:=len-1;fa:=1;stop:=false; while (fa*2len)or(heapfa*2heapson then begin tmp:=heapfa; heapfa:=heapson; heapson:=tmp; fa:=son; end else stop:=true; end; end;,常州市第一中学 林厚从,堆结构及其应用,begin main assign(input,fruit.in); reset(input); assign(output,fruit.out);rewrite(output); len:=0;readln(n); for i:=1 to n do 建堆 begin read(tmp);put(tmp); end; ans:=0; for i:=1 to n-1 do 取、统计、插入 begin a:=get;b:=get; ans:=ans+a+b;put(a+b); end; writeln(ans); close(input);close(output); end.,常州市第一中学 林厚从,堆结构及其应用,下面介绍更为高效的算法： 设置两个表A和B，其中表A放原n堆果子数，并按由小到大排列(注)；表B放新合并的果子数，因为后合并的果子数不会少于以前合并的果子数，所以新加入的数一定插在表B的尾部。每次合并分两步:(1)在A和B的头部取数（分3种情况aa 、ab 、 bb ); （2）合并后的新数加入B的尾部。整个合并的时间复杂度降为 O(n) 。 注： 因为n堆果子数20000，表A的排序可以用统计表来实现： a:array120000 of longint; ai为原n堆果子数是i的堆数，这样整个算法的时间复杂度为O(n),空间复杂度是O(20000)。,常州市第一中学 林厚从,堆结构及其应用,二、堆排序问题 例2、堆排序(heapsort.?) 【问题描述】 假设n个数存放在A1n中，我们可以利用堆将它们从小到大进行排序，这种排序方法，称为“堆排序”。输入两行，第1行为n，第2行为n个整数，每个数之间用1个空格隔开。输出1行，为从小到大排好序的n个数，每个数之间也用1个空格隔开。,【问题分析】 一种思路是完全按照上一个例题的方法去做，程序见heapsort1.pas；,二是考虑这样两个问题，一是如何构建一个初始（大根）堆？二是确定了最大值后（堆顶元素A1即为最大值），如何在剩下的n-1个数中，调整堆结构产生次大值？,常州市第一中学 林厚从,堆结构及其应用,对于第一个问题，我们可以这样理解，首先所有叶结点（编号为trunc(N/2)+1到N）都各自成堆，我们只要从最后一个分支结点（编号为trunc(N/2)）开始，不断“调整”每个分支结点与孩子结点的值，使它们满足堆的要求，直到根结点为止，这样一定能确保根（堆顶元素）的值最大。 “调整”的思想如下：即如果当前结点编号为i, 则它的左孩子为2*i, 右孩子2*i+1,首先比较Ai与MAX（A2*i，A2*i+1）；如果Ai大，说明以结点i为根的子树已经是堆，不用再调整。否则将结点i和左右孩子中值大的那个结点j互换位置，互换后可能破坏以j为根的堆，所以必须再比较Aj 与MAX（A2*j，A2*j+1）,依此类推，直到父结点的值大于等于两个孩子或出现叶结点为止。这样，以i为根的子树就被调整成为一个堆。,常州市第一中学 林厚从,堆结构及其应用,Procedure heap(Var r:arrtype；nn,ii:Integer)；一次操作，使r满足堆的性质， Var x,i,j:Integer； 得到1个最大数在rii中 Begin i:=ii； x:=rii； 把待调整的结点值暂存起来 j:=2*ii； j存放i的孩子中值大的结点编号，开始时为i的左孩子编号 While j=nn Do 不断调整，使以i为根的二叉树满足堆的性质 Begin If (jnn) And (rjrj+1) Then j:=j+1； 若i有右孩子且值比左孩子大，则把j设为右孩子的编号 If xrj Then Begin ri:=rj；i:=j；j:=2*i End 若父结点比孩子结点小，则调整父结点和孩子结点中值大的那个结点，确保此处满足堆的性质 Else j:=nn+1； 故意让j超出范围，终止循环 End； ri:=x； 调整到最终位置 End；,常州市第一中学 林厚从,堆结构及其应用,经过第一步骤建立好一个初始堆后，可以确定堆顶元素值最大，我们就把它（A1）与最后一个元素（AN）交换，然后再对A1N-1进行调整，得到次大值与AN-1交换，如此下去，所有元素便有序存放了。 主程序的框架如下，详细程序见heapsort2.pas： Const max=100000； Type arrtype=Array1max Of Integer； Var a:arrtype；i,n,temp:Integer； Begin 输入n和n个元素； For i:=n Div 2 Downto 1 Do heap(a,n,i)； 建立初始堆，且产生最大值A1 For i:=n Downto 2 Do 将当前最大值交换到最终位置上，再对前i-1个数调整 Begin temp:=a1；a1:=ai；ai:=temp； heap(a,i-1,1)； End； 输出； End.,常州市第一中学 林厚从,堆结构及其应用,【小结】 堆排序在数据较少时并不值得提倡，但数据量很大时，效率就会很高。因为其运算的时间主要消耗在建立初始堆和调整过程中，堆排序的时间复杂度为O（nlog2n），而且堆排序只需一个供交换用的辅助单元空间，是一种不稳定的排序方法。,常州市第一中学 林厚从,堆结构及其应用,例3、鱼塘钓鱼（fishing）,【问题分析】 算法1： 我们可以这样想：如果知道了