已阅读5页，还剩35页未读， 继续免费阅读
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
堆及其应用,江苏省华罗庚中学杨志军,堆的定义,01,堆的性质,02,堆的基本操作,03,堆的应用,04,TableofContents,内容大纲,预备知识,完全二叉树：如果一棵深度为K的二叉树，1至K-1层的结点都是满的，即满足2i-1(1ai;for(inti=1;i=n;i+)put(ai);方法二：直接对数组a进行调整，从andiv2开始向下调整成堆，然后对andiv2-1调整,直至a1。,堆的应用,例1、堆排序假设n个随机整数存放在A1.n中，我们可以利用堆将它们从小到大进行排序，这种排序方法，称为“堆排序”。【问题分析】(1)建立小根堆(2)取出根结点并调整堆：将根结点输出，并与小根堆的最后一个结点交换，再从上到下进行调整，使其仍为小根堆，重复(2)操作，最后输出数组。Pascal:fori:=1tondowriteln(get);C+:for(inti=1;i=n;i+)coutget()n;heap1=1;len=1;while(in)k1=k2;k2=get();if(k1!=k2)i+;put(k2*2);put(k2*3);put(k2*5);put(k2*7);coutk2endl;,判断前后两次取出的数是否一样,把生成的新数加入到堆中,堆的应用,例3、合并果子（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（1n;for(inti=1;ix;put(x);for(inti=1;i=n-1;i+)inta=get(),b=get();sum=sum+a+b;put(a+b);coutsumendl;,堆的应用,【时间复杂度】get和put操作的复杂度均为log2n。所以建堆复杂度为nlog2n。合并果子时，每次需要从堆中取出两个数，然后再加入一
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论