NOIP普及讲座8-堆及其应用

1、堆及其应用,堆的定义,01,堆的性质,02,堆的基本操作,03,堆的应用,04,Table of Contents,内容大纲,预备知识,完全二叉树： 如果一棵深度为K的二叉树，1至K-1层的结点都是满的，即满足2i-1(1=i=k-1),只有最下面的一层的结点数小于等于2k-1，并且最下面一层的结点都集中在该层最左边的若干位置，则此二叉树称为完全二叉树,预备知识,堆的定义,堆也称二叉堆，结构上是一种数组，本质上是一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应,堆的性质,树根为A1，利用完全二叉树的性质，可以求出第i个结点的父结点、左孩子结点、右孩子结点的下标分别为：trun

2、c(i/2)、2i、2i+1,堆的性质,二叉堆还具有这样一个重要的性质：对除根以外的每个结点i，Aparent(i)Ai，即所有结点的值都不得超过其父结点的值，称为大根堆。小根堆就是要求：Aparent(i)Ai,堆的基本操作,使用堆的关键部分是两个基本操作： Put操作：即往堆中加入一个结点。 方法是往堆尾加入一个结点，并通过从下往上的调整法，使其继续保持堆的性质； Get操作：即从堆中取出根结点。 方法是从堆中取出堆头结点，并删除该结点(堆尾覆盖)，再通过从上往下的调整法，使其继续保持堆的性质,Put操作,heap,Put操作,5,7,5,6,1,4,4,3,2,1,heap,Put操作,

3、5,7,5,6,1,4,4,3,2,1,heap,son,Put操作,5,7,5,1,6,4,4,3,2,1,heap,son,Put操作,5,7,5,4,6,1,4,3,2,1,heap,son,Put操作,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 temp:=heapson div 2; heapson div 2:=heapson; heapson:=te

4、mp; son:=son div 2; end; end,Put操作,void put(int x) int fa,son,tmp; len+;heaplen=x;son=len; while (son!=1,Get操作,5,7,5,4,6,1,4,3,2,1,heap,Get操作,5,7,5,4,6,1,4,3,2,1,heap,Get操作,5,7,5,4,1,4,3,2,6,heap,pa,Get操作,5,7,5,4,6,4,3,2,1,heap,pa,Get操作,5,7,5,6,4,4,3,2,1,heap,pa,function get:longint; var pa,son,tmp:

5、longint; begin get:=heap1; heap1:=heaplen; len:=len-1; pa:=1; while pa*2len) or (heappa*2heapson then begin tmp:=heappa; heappa:=heapson; heapson:=tmp; pa:=son; end else break; end; end,int get() int p=heap1,pa=1,son,tmp; heap1=heaplen;len-; while (pa*2len | heappa*2heapson) tmp=heappa; heappa=heaps

6、on; heapson=tmp; pa=son; else return p; return p;,建立堆,方法一：对数组中的每个数依次进行插入操作; Pascal: for i:=1 to n do read(ai); for i:=1 to n do put(ai); C+: for (int i=1;iai; for (int i=1;i=n;i+) put(ai); 方法二：直接对数组a进行调整，从an div 2开始向下调整成堆，然后对an div 2-1调整,直至a1,堆的应用,例1、堆排序 假设n个随机整数存放在A1.n中，我们可以利用堆将它们从小到大进行排序，这种排序方法，称为

7、“堆排序”。 【问题分析】 (1) 建立小根堆 (2) 取出根结点并调整堆：将根结点输出，并与小根堆的最后一个结点交换，再从上到下进行调整，使其仍为小根堆，重复(2)操作，最后输出数组。 Pascal: for i:=1 to n do writeln(get); C+: for (int i=1;i=n;i+) coutget()endl,堆的应用,小结】 堆排序在数据较少时并不值得提倡，但数据量很大时，效率就会很高。因为其运算的时间主要消耗在建立初始堆和调整过程中，堆排序的时间复杂度为O（nlog2n），而且堆排序只需一个供交换用的辅助单元空间，是一种不稳定的排序方法,堆的应用,例2、丑数

8、（H数） 丑数是指素因子都在集合2，3，5，7的数，求第n大的丑数(n6000) ，第一个丑数是1。 【问题分析】 穷举显然不行，尝试用“构造法”不断生成丑数； 构造的基本思想：5个线性表，时间复杂度O(n2) 其中的关键操作：取最小结点、插入新结点； 可以利用二叉堆(小根堆)的基本操作。,堆的应用,readln(n); heap1:=1; len:=1; i:=0; k1:=0; k2:=0; while ik2 then begin i:=i+1; put(k2*2); put(k2*3); put(k2*5); put(k2*7); end; end; writeln(k2,判断前后两次

9、取出的数是否一样,把生成的新数加入到堆中,堆的应用,cinn; 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+) 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一

10、起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和,堆的应用,因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最

11、小的体力耗费值,堆的应用,输入文件】 输入文件fruit.in包括两行，第一行是一个整数n（1=n=30000），表示果子的种类数。 第二行包含n个整数，用空格分隔，第i个整数ai（1=ai=20000）是第i种果子的数目。 【输出文件】 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231,堆的应用,算法分析】 (1)可以看作是n个叶子结点，每个结点有一个权值Wi，将它们中两个、两个合并为树，假设每个结点从根到它的距离是Di，使得最终(wi * di)最小。 即为求最优二叉树问题，这样该问题就变为构造哈夫曼树，求最小代价问题了。 (2

12、) 算法: a.从森林里取两个权和最小的结点； b.将它们的权和相加，得到新的结点，并且把原结点删除，将新结点插入到森林中； c.重复(a)(b)，直到整个森林里只有一棵树,堆的应用,算法实现】 该问题是贪心算法，可用堆的两个基本操作来实现：首先，建立小根堆，并不断重复如下操作：分别读取两个最小数累加起来，并且形成一个新的结点，将新结点插入到堆的尾部。利用堆调整使整个数组仍然是最小堆，重复此操作，直到仅有一个结点,堆的应用,堆的应用,堆的应用,len:=0; read(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,堆的应用,sum=0; cinn; for (int i=1;ix; put(x); fo