NOIP普与讲座堆与其应用

1、NOIP普与讲座堆与其应用NOIP普与讲座堆与其应用01020304Table of Contents内容大纲内容大纲NOIP普与讲座堆与其应用预备知识 完全二叉树：完全二叉树：如果一棵深度为如果一棵深度为K K的二叉树，的二叉树，1 1至至K-1K-1层层的结点都是满的，即满足的结点都是满的，即满足2 2i-1i-1(1=i=k-1),(1=i=k-1),只有最下面的一层的结点数小于等于只有最下面的一层的结点数小于等于2 2k-1k-1，并且最下面一层的结点都集中在该层最左并且最下面一层的结点都集中在该层最左边的若干位置，则此二叉树称为完全二叉边的若干位置，则此二叉树称为完全二叉树。树。NO

2、IP普与讲座堆与其应用预备知识1 12 23 34 45 56 67 7满二叉树满二叉树1 12 23 34 45 5完全二叉树完全二叉树NOIP普与讲座堆与其应用堆的定义 堆也称二叉堆，结构上是一种数组，本质堆也称二叉堆，结构上是一种数组，本质上是一棵完全二叉树。树中每个结点与数上是一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应。组中存放该结点中值的那个元素相对应。NOIP普与讲座堆与其应用堆的性质 树根为树根为A1A1，利用完全二叉树的性质，可，利用完全二叉树的性质，可以求出第以求出第i i个结点的父结点、左孩子结点、个结点的父结点、左孩子结点、右孩子结点的下标分别为：

3、右孩子结点的下标分别为：trunc(i/2)trunc(i/2)、2i2i、2i+12i+1。NOIP普与讲座堆与其应用堆的性质 二叉堆还具有这样一个重要的性质：对除根以外二叉堆还具有这样一个重要的性质：对除根以外的每个结点的每个结点i i，Aparent(i)AiAparent(i)Ai，即所有结，即所有结点的值都不得超过其父结点的值，称为大根堆。点的值都不得超过其父结点的值，称为大根堆。小根堆就是要求：小根堆就是要求：Aparent(i)Ai Aparent(i)Ai 。NOIP普与讲座堆与其应用堆的基本操作 使用堆的关键部分是两个基本操作：使用堆的关键部分是两个基本操作：PutPut操作

4、：即往堆中加入一个结点。操作：即往堆中加入一个结点。方法是往堆尾加入一个结点，并通过从下往方法是往堆尾加入一个结点，并通过从下往上的调整法，使其继续保持堆的性质；上的调整法，使其继续保持堆的性质；GetGet操作：即从堆中取出根结点。操作：即从堆中取出根结点。方法是从堆中取出堆头结点，并删除该结点方法是从堆中取出堆头结点，并删除该结点( (堆尾覆盖堆尾覆盖) )，再通过从上往下的调整法，使其继，再通过从上往下的调整法，使其继续保持堆的性质；续保持堆的性质； NOIP普与讲座堆与其应用Put操作575644321142564375heapheapNOIP普与讲座堆与其应用Put操作1425643

5、7557561443211425643751heapheapNOIP普与讲座堆与其应用Put操作14256437515756144321heapheap1425143756sonsonNOIP普与讲座堆与其应用Put操作14251437565751644321heapheap1125443756sonsonNOIP普与讲座堆与其应用Put操作11254437565754614321heapheapsonsonNOIP普与讲座堆与其应用Put操作procedure put(x:longint);procedure put(x:longint);var fa,son,tmp:longint;var

6、 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

7、; heapson:=temp; son:=son div 2; son:=son div 2; end; end;end;end;NOIP普与讲座堆与其应用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=heap

8、son;heapson/2=heapson;heapson=tmp;heapson=tmp;son=son/2;son=son/2; NOIP普与讲座堆与其应用Get操作11254437565754614321heapheapNOIP普与讲座堆与其应用Get操作11254437565754614321heapheap612544375NOIP普与讲座堆与其应用Get操作612544375575414326heapheap162544375papaNOIP普与讲座堆与其应用Get操作162544375575464321heapheap142564375papaNOIP普与讲座堆与其应用Get操作

9、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* *2heappa2heap

10、son 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-;

11、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; NOIP普与讲座堆与其应用建立堆 方法一：对数组中的每个数依次进行插入操作方法一：对数组中的每个数依次进行插入操作; ; Pa

12、scal: 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-

13、1an div 2-1调整调整, ,直至直至a1a1。NOIP普与讲座堆与其应用堆的应用例例1 1、堆排序、堆排序 假设假设n n个随机整数存放在个随机整数存放在A1.nA1.n中，我们可以利用堆将中，我们可以利用堆将它们从小到大进行排序，这种排序方法，称为它们从小到大进行排序，这种排序方法，称为“堆排序堆排序”。【问题分析问题分析】(1) (1) 建立小根堆建立小根堆(2) (2) 取出根结点并调整堆：将根结点输出，并与小根堆的最取出根结点并调整堆：将根结点输出，并与小根堆的最后一个结点交换，再从上到下进行调整，使其仍为小根堆，后一个结点交换，再从上到下进行调整，使其仍为小根堆，重复重复(2

14、)(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;NOIP普与讲座堆与其应用堆的应用【小结小结】 堆排序在数据较少时并不值得提倡，但数据堆排序在数据较少时并不值得提倡，但数据量很大时，效率就会很高。因为其运算的时间主量很大时，效率就会很高。因为其运算的时间主要消耗在建立初始堆和调整过程中，堆排序的时要

15、消耗在建立初始堆和调整过程中，堆排序的时间复杂度为间复杂度为O O（nlognlog2 2n n），而且堆排序只需一个供），而且堆排序只需一个供交换用的辅助单元空间，是一种不稳定的排序方交换用的辅助单元空间，是一种不稳定的排序方法。法。NOIP普与讲座堆与其应用堆的应用例例2 2、丑数（、丑数（H H数）数） 丑数是指素因子都在集合丑数是指素因子都在集合22，3 3，5 5，77的数，的数，求第求第n n大的丑数大的丑数(n6000) (n6000) ，第一个丑数是，第一个丑数是1 1。【问题分析问题分析】穷举显然不行，尝试用穷举显然不行，尝试用“构造法构造法”不断生成丑数；不断生成丑数；构造

16、的基本思想：构造的基本思想：5 5个线性表，时间复杂度个线性表，时间复杂度O(n2)O(n2)其中的关键操作：取最小结点、插入新结点；其中的关键操作：取最小结点、插入新结点；可以利用二叉堆可以利用二叉堆( (小根堆小根堆) )的基本操作。的基本操作。NOIP普与讲座堆与其应用堆的应用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;

17、 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);判断前后两次取出的数是否一样把生成的新数加入到堆中NOIP普与讲座堆与其应用堆的应用cinn;cinn;heap1=1; len=1;heap1=1; len=1;while (in)while (in) k1=k2; k2

18、=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;判断前后两次取出的数是否一样把生成的新数加入到堆中NOIP普与讲座堆与其应用堆的应用例例3 3、合并果子（、合并果子（NOIP2004NOIP2004高中组第高中组第2 2题）题）【问题描述问题描述】fruit.?(pas,c,c+)fruit.?(pas,c,c+) 在一个果园里

19、，多多已经将所有的果子打了在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过看出，所有的果子经过n-1n-1次合并之后，就只剩下次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。每次合并所耗体力之和。NOIP普与讲座堆与其应用堆的应用因为还要花大力气把这些果子搬回家，所以多因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个多在合并果子时要尽可能地节省体力。假定每个果子重量都为果子重量都为1 1，并且已知果子的种类数和每种果，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力使多多耗费的体力最少，