NOIP普及讲座8 堆及其应用ppt课件

堆及其应用 江苏省华罗庚中学杨志军 堆的定义 01 堆的性质 02 堆的基本操作 03 堆的应用 04 TableofContents 内容大纲 预备知识 完全二叉树 如果一棵深度为K的二叉树 1至K 1层的结点都是满的 即满足2i 1 1 i k 1 只有最下面的一层的结点数小于等于2k 1 并且最下面一层的结点都集中在该层最左边的若干位置 则此二叉树称为完全二叉树 预备知识 堆的定义 堆也称二叉堆 结构上是一种数组 本质上是一棵完全二叉树 树中每个结点与数组中存放该结点中值的那个元素相对应 堆的性质 树根为A 1 利用完全二叉树的性质 可以求出第i个结点的父结点 左孩子结点 右孩子结点的下标分别为 trunc i 2 2i 2i 1 堆的性质 二叉堆还具有这样一个重要的性质 对除根以外的每个结点i A parent i A i 即所有结点的值都不得超过其父结点的值 称为大根堆 小根堆就是要求 A parent i A i 堆的基本操作 使用堆的关键部分是两个基本操作 Put操作 即往堆中加入一个结点 方法是往堆尾加入一个结点 并通过从下往上的调整法 使其继续保持堆的性质 Get操作 即从堆中取出根结点 方法是从堆中取出堆头结点 并删除该结点 堆尾覆盖 再通过从上往下的调整法 使其继续保持堆的性质 Put操作 heap Put操作 5 7 5 6 1 4 4 3 2 1 heap Put操作 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操作 procedureput x longint varfa son tmp longint beginlen len 1 heap len x son len while son1 and heap sondiv2 heap son dobegintemp heap sondiv2 heap sondiv2 heap son heap son temp son sondiv2 end end Put操作 voidput intx intfa son tmp len heap len 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 functionget longint varpa son tmp longint beginget heap 1 heap 1 heap len len len 1 pa 1 whilepa 2len or heap pa 2 heap son thenbegintmp heap pa heap pa heap son heap son tmp pa son endelsebreak end end intget intp heap 1 pa 1 son tmp heap 1 heap len len while pa 2len heap pa 2 heap son tmp heap pa heap pa heap son heap son tmp pa son elsereturnp returnp 建立堆 方法一 对数组中的每个数依次进行插入操作 Pascal fori 1tondoread a i fori 1tondoput a i C for inti 1 i a i for inti 1 i n i put a i 方法二 直接对数组a进行调整 从a ndiv2 开始向下调整成堆 然后对a ndiv2 1 调整 直至a 1 堆的应用 例1 堆排序假设n个随机整数存放在A 1 n 中 我们可以利用堆将它们从小到大进行排序 这种排序方法 称为 堆排序 问题分析 1 建立小根堆 2 取出根结点并调整堆 将根结点输出 并与小根堆的最后一个结点交换 再从上到下进行调整 使其仍为小根堆 重复 2 操作 最后输出数组 Pascal fori 1tondowriteln get C for inti 1 i n i cout get endl 堆的应用 小结 堆排序在数据较少时并不值得提倡 但数据量很大时 效率就会很高 因为其运算的时间主要消耗在建立初始堆和调整过程中 堆排序的时间复杂度为O nlog2n 而且堆排序只需一个供交换用的辅助单元空间 是一种不稳定的排序方法 堆的应用 例2 丑数 H数 丑数是指素因子都在集合 2 3 5 7 的数 求第n大的丑数 n 6000 第一个丑数是1 问题分析 穷举显然不行 尝试用 构造法 不断生成丑数 构造的基本思想 5个线性表 时间复杂度O n2 其中的关键操作 取最小结点 插入新结点 可以利用二叉堆 小根堆 的基本操作 堆的应用 readln n heap 1 1 len 1 i 0 k1 0 k2 0 whileik2thenbegini i 1 put k2 2 put k2 3 put k2 5 put k2 7 end end writeln k2 判断前后两次取出的数是否一样 把生成的新数加入到堆中 堆的应用 cin n heap 1 1 len 1 while i n k1 k2 k2 get if k1 k2 i put k2 2 put k2 3 put k2 5 put k2 7 cout k2 endl 判断前后两次取出的数是否一样 把生成的新数加入到堆中 堆的应用 例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 1 ai 20000 是第i种果子的数目 输出文件 输出文件fruit out包括一行 这一行只包含一个整数 也就是最小的体力耗费值 输入数据保证这个值小于231 堆的应用 算法分析 1 可以看作是n个叶子结点 每个结点有一个权值W i 将它们中两个 两个合并为树 假设每个结点从根到它的距离是D i 使得最终 wi di 最小 即为求最优二叉树问题 这样该问题就变为构造哈夫曼树 求最小代价问题了 2 算法 a 从森林里取两个权和最小的结点 b 将它们的权和相加 得到新的结点 并且把原结点删除 将新结点插入到森林中 c 重复 a b 直到整个森林里只有一棵树 堆的应用 算法实现 该问题是贪心算法 可用堆的两个基本操作来实现 首先 建立小根堆 并不断重复如下操作 分别读取两个最小数累加起来 并且形成一个新的结点 将新结点插入到堆的尾部 利用堆调整使整个数组仍然是最小堆 重复此操作 直到仅有一个结点 堆的应用 堆的应用 堆的应用 len 0 read n fori 1tondobeginread tmp put tmp end ans 0 fori 1ton 1dobegina get b get ans ans a b put a b end writeln ans 堆的应用 sum 0 cin n for inti 1 i x put x