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

01020304Table of Contents内容大纲预备知识完全二叉树：完全二叉树：如果一棵深度为如果一棵深度为K K的二叉树，的二叉树，1 1至至K-1K-1层层的结点都是满的，即满足的结点都是满的，即满足2 2i-1i-1(1=i=k-1),(1=i=k-1),只有最下面的一层的结点数小于等于只有最下面的一层的结点数小于等于2 2k-1k-1，并且最下面一层的结点都集中在该层最左并且最下面一层的结点都集中在该层最左边的若干位置，则此二叉树称为完全二叉边的若干位置，则此二叉树称为完全二叉树。树。预备知识1 12 23 34 45 56 67 7满二叉树满二叉树1 12 23 34 45 5完全二叉树完全二叉树堆的定义堆也称二叉堆，结构上是一种数组，本质堆也称二叉堆，结构上是一种数组，本质上是一棵完全二叉树。树中每个结点与数上是一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应。组中存放该结点中值的那个元素相对应。堆的性质树根为树根为A1A1，利用完全二叉树的性质，可，利用完全二叉树的性质，可以求出第以求出第i i个结点的父结点、左孩子结点、个结点的父结点、左孩子结点、右孩子结点的下标分别为：右孩子结点的下标分别为：trunc(i/2)trunc(i/2)、2i2i、2i+12i+1。堆的性质 二叉堆还具有这样一个重要的性质：对除根以外二叉堆还具有这样一个重要的性质：对除根以外的每个结点的每个结点i i，Aparent(i)AiAparent(i)Ai，即所有结，即所有结点的值都不得超过其父结点的值，称为大根堆。点的值都不得超过其父结点的值，称为大根堆。小根堆就是要求：小根堆就是要求：Aparent(i)Ai Aparent(i)Ai 。堆的基本操作 使用堆的关键部分是两个基本操作：使用堆的关键部分是两个基本操作：PutPut操作：即往堆中加入一个结点。操作：即往堆中加入一个结点。方法是往堆尾加入一个结点，并通过从下往方法是往堆尾加入一个结点，并通过从下往上的调整法，使其继续保持堆的性质；上的调整法，使其继续保持堆的性质；GetGet操作：即从堆中取出根结点。操作：即从堆中取出根结点。方法是从堆中取出堆头结点，并删除该结点方法是从堆中取出堆头结点，并删除该结点( (堆尾覆盖堆尾覆盖) )，再通过从上往下的调整法，使其继，再通过从上往下的调整法，使其继续保持堆的性质；续保持堆的性质； Put操作575644321142564375heapheapPut操作14256437557561443211425643751heapheapPut操作14256437515756144321heapheap1425143756sonsonPut操作14251437565751644321heapheap1125443756sonsonPut操作11254437565754614321heapheapsonsonPut操作procedure put(x:longint);procedure put(x:longint);var fa,son,tmp:longint;var fa,son,tmp:longint;beginbegin len:=len+1; heaplen:=x; son:=len; len:=len+1; heaplen:=x; son:=len; while (son1) and (heapson div 2heapson) do while (son1) and (heapson div 2heapson) do begin begin temp:=heapson div 2; temp:=heapson div 2; heapson div 2:=heapson; heapson div 2:=heapson; heapson:=temp; heapson:=temp; son:=son div 2; son:=son div 2; end; end;end;end;Put操作void put(int x)void put(int x) int fa,son,tmp;int fa,son,tmp;len+;len+;heaplen=x;heaplen=x;son=len;son=len;while (son!=1 & heapson/2heapson)while (son!=1 & heapson/2heapson) tmp=heapson/2;tmp=heapson/2;heapson/2=heapson;heapson/2=heapson;heapson=tmp;heapson=tmp;son=son/2;son=son/2; Get操作11254437565754614321heapheapGet操作11254437565754614321heapheap612544375Get操作612544375575414326heapheap162544375papaGet操作162544375575464321heapheap142564375papaGet操作142564375575644321heapheappapafunction get:longint;function get:longint;var pa,son,tmp:longint;var pa,son,tmp:longint;beginbegin get:=heap1; heap1:=heaplen; len:=len-1; pa:=1; get:=heap1; heap1:=heaplen; len:=len-1; pa:=1; while pa while pa* *2=len do2len) or (heappa2+1len) or (heappa* *2heappa2heapson if heappaheapson then begin then begin tmp:=heappa; heappa:=heapson; tmp:=heappa; heappa:=heapson; heapson:=tmp; pa:=son; heapson:=tmp; pa:=son; end end else break; else break; end; end;end;end;int get()int get() int p=heap1,pa=1,son,tmp;int p=heap1,pa=1,son,tmp;heap1=heaplen;heap1=heaplen;len-;len-;while (pawhile (pa* *2=len)2len | heappa2+1len | heappa* *2heappa2heapson)if (heappaheapson) tmp=heappa;tmp=heappa;heappa=heapson;heappa=heapson;heapson=tmp;heapson=tmp;pa=son;pa=son; else return p;else return p; return p;return p; 建立堆 方法一：对数组中的每个数依次进行插入操作方法一：对数组中的每个数依次进行插入操作; ; Pascal: Pascal:for i:=1 to n do read(ai);for i:=1 to n do read(ai); for i:=1 to n do put(ai);for i:=1 to n do put(ai); C+: C+:for (int i=1;iai;for (int i=1;iai; for (int i=1;i=n;i+) put(ai);for (int i=1;i=n;i+) put(ai); 方法二：直接对数组方法二：直接对数组a a进行调整，从进行调整，从an div 2an div 2开始向下调整成堆，然后对开始向下调整成堆，然后对an div 2-1an div 2-1调整调整, ,直至直至a1a1。堆的应用例例1 1、堆排序、堆排序 假设假设n n个随机整数存放在个随机整数存放在A1.nA1.n中，我们可以利用堆将中，我们可以利用堆将它们从小到大进行排序，这种排序方法，称为它们从小到大进行排序，这种排序方法，称为“堆排序堆排序”。【问题分析问题分析】(1) (1) 建立小根堆建立小根堆(2) (2) 取出根结点并调整堆：将根结点输出，并与小根堆的最取出根结点并调整堆：将根结点输出，并与小根堆的最后一个结点交换，再从上到下进行调整，使其仍为小根堆，后一个结点交换，再从上到下进行调整，使其仍为小根堆，重复重复(2)(2)操作，最后输出数组。操作，最后输出数组。Pascal:Pascal:for i:=1 to n do writeln(get);for i:=1 to n do writeln(get);C+:C+:for (int i=1;i=n;i+) coutget()endl;for (int i=1;i=n;i+) coutget()endl;堆的应用【小结小结】 堆排序在数据较少时并不值得提倡，但数据堆排序在数据较少时并不值得提倡，但数据量很大时，效率就会很高。因为其运算的时间主量很大时，效率就会很高。因为其运算的时间主要消耗在建立初始堆和调整过程中，堆排序的时要消耗在建立初始堆和调整过程中，堆排序的时间复杂度为间复杂度为O O（nlognlog2 2n n），而且堆排序只需一个供），而且堆排序只需一个供交换用的辅助单元空间，是一种不稳定的排序方交换用的辅助单元空间，是一种不稳定的排序方法。法。堆的应用例例2 2、丑数（、丑数（H H数）数） 丑数是指素因子都在集合丑数是指素因子都在集合22，3 3，5 5，77的数，的数，求第求第n n大的丑数大的丑数(n6000) (n6000) ，第一个丑数是，第一个丑数是1 1。【问题分析问题分析】穷举显然不行，尝试用穷举显然不行，尝试用“构造法构造法”不断生成丑数；不断生成丑数；构造的基本思想：构造的基本思想：5 5个线性表，时间复杂度个线性表，时间复杂度O(n2)O(n2)其中的关键操作：其中的关键操作：取最小结点、插入新结点；取最小结点、插入新结点；可以利用二叉堆可以利用二叉堆( (小根堆小根堆) )的基本操作。的基本操作。堆的应用readln(n);readln(n);heap1:=1; len:=1;heap1:=1; len:=1;i:=0; k1:=0; k2:=0;i:=0; k1:=0; k2:=0;while in dowhile in dobeginbegin k1:=k2; k2:=get; k1:=k2; k2:=get; if k1k2 if k1k2 then begin then begin i:=i+1; i:=i+1; put(k2 put(k2* *2); put(k22); put(k2* *3);3); put(k2 put(k2* *5); put(k25); put(k2* *7);7); end; end;end;end;writeln(k2);writeln(k2);判断前后两次取出的数是否一样把生成的新数加入到堆中堆的应用cinn;cinn;heap1=1; len=1;heap1=1; len=1;while (in)while (in) k1=k2; k2=get();k1=k2; k2=get();if (k1!=k2)if (k1!=k2) i+;i+;put(k2put(k2* *2);2);put(k2put(k2* *3);3);put(k2put(k2* *5);5);put(k2put(k2* *7);7); coutk2endl;coutk2endl;判断前后两次取出的数是否一样把生成的新数加入到堆中堆的应用例例3 3、合并果子（、合并果子（NOIP2004NOIP2004高中组第高中组第2 2题）题）【问题描述问题描述】fruit.?(pas,c,c+)fruit.?(pas,c,c+) 在一个果园里，多多已经将所有的果子打了在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过看出，所有的果子经过n-1n-1次合并之后，就只剩下次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。每次合并所耗体力之和。堆的应用因为还要花大力气把这些果子搬回家，所以多因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个多在合并果子时要尽可能地节省体力。假定每个果子重量都为果子重量都为1 1，并且已知果子的种类数和每种果，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力使多多耗费的体力最少，并输出这个最小的体力耗费值。耗费值。 例如有例如有3 3种果子，数目依次为种果子，数目依次为1 1，2 2，9 9。可以。可以先将先将1 1、2 2堆合并，新堆数目为堆合并，新堆数目为3 3，耗费体力为，耗费体力为3 3。接着，将新堆与原先的第三堆合并，又得到新的接着，将新堆与原先的第三堆合并，又得到新的堆，数目为堆，数目为1212，耗费体力为，耗费体力为 1212。所以多多总共耗。所以多多总共耗费体力费体力=3+12=15=3+12=15。可以证明。可以证明1515为最小的体力耗费为最小的体力耗费值。值。堆的应用【输入文件输入文件】 输入文件输入文件fruit.infruit.in包括两行，第一行是一个包括两行，第一行是一个整数整数n n（1=n=300001=n=30000），表示果子的种类数。），表示果子的种类数。 第二行包含第二行包含n n个整数，用空格分隔，第个整数，用空格分隔，第i i个整个整数数aiai（1=ai=200001=ain;cinn;for (int i=1;i=n;i+)for (int i=1;ix;cinx;put(x);put(x); for (int i=1;i=n-1;i+)for (int i=1;i=n-1;i+) int a=get(),b=get();int a=get(),b=get();sum=sum+a+b;sum=sum+a+b;put(a+b);put(a+b); coutsumendl;coutsumendl;堆的应用【时间复杂度时间复杂度】 get get和和putput操作的复杂度均为操作的复杂度均为loglog2 2n n。所以建堆。所以建堆复杂度为复杂度为nlognlog2 2n n。 合并果子时，每次需要从堆中取出两个数，合并果子时，每次需要从堆中取出两个数，然后再加入一个数，因此一次合并的复杂度为然后再加入一个数，因此一次合并的复杂度为3log3log2 2n n，共，共n-1n-1次。次。 所以整道题目的复杂度是所以整道题目的复杂度是nlognlog2 2n n。