二叉堆及其应用

1、二叉堆及其应用雅礼 朱全民一个基本问题 写一种数据结构，完成以下3种操作： (操作的总次数不超过100000) 1、插入一个数 2、询问最小值 3、删除最小值 要求是这3种操作都要快。输入输出输入每行一次操作，有如下三种：1 x：表示插入X这个数2 ：表示询问当前最小值3： 表示删除最小值输出对于每个询问最小值操作，输出一行，每行仅一个数，表示当前的最小值。输入：9 - 9次操作1 2021 301 1023232输出：20102030样例用线性表作为数据结构 无序表： 插入操作 O（1） 询问最小值 O（n） 删除最小值 O（n） 有序表： 插入操作 O（n） 询问最小值 O（1） 删除最小

2、值 O（1）二叉堆 定义定义堆是一棵完全二叉树，对于每一个非叶子结点，堆是一棵完全二叉树，对于每一个非叶子结点，它的权值都不大于（或不小于）左右孩子的权值，它的权值都不大于（或不小于）左右孩子的权值，我们称这样的堆为小根堆（或大根堆）。我们称这样的堆为小根堆（或大根堆）。 描述如下描述如下:n个元素的序列个元素的序列k1,k2,kn，当且仅当满足，当且仅当满足 ki=k2i 并且并且 ki =k2i 并且并且 ki = k2i+1 二叉堆肯定是一颗完全二叉树二叉堆肯定是一颗完全二叉树在堆中插入元素x 首先将元素首先将元素x放到堆中的最后一个位置（即最放到堆中的最后一个位置（即最底层最右边的位置

3、），然后不断地把底层最右边的位置），然后不断地把x往上调往上调整，直到整，直到x调不动为止（即大于它现在的父亲，调不动为止（即大于它现在的父亲，或者或者x处于根结点）。处于根结点）。定义一个堆:Var st:array1.maxn of longint; /存储堆 n:longint; /堆中元素个数13545786213557864(1)将新节点插到最后(2)把新节点和父亲进行交换1557864(3)继续交换，直到重新满足堆的性质322插入 (实际上是不断向上调整的过程) PROC up (k:longint); 把第k个结点上调 begin while k1 do begin i:=k d

4、iv 2; i是k的父亲 if stistk then begin swap(i,k); k:=i; 交换结点i和k end else exit; end; end;在堆中删除任意一个元素 这里说指的删除任意一个元素，是指在当前堆中位置为w的元素。过程如下：首先把位置w的元素和最后一个位置的元素交换，然后删去最后一个位置，这样w上的元素就被删除了。接着把位置w上的新元素不断下调，直到满足堆的性质。 155786431557864315578634(1)当前要删除的节点是根节点的左儿子(2)将根节点的左儿子和最后一个节点交换(3)将新的节点不断下调，直到满足堆的性质22删除 (实际上是不断向下调

5、整的过程)PROC down(k:longint);把第k个结点往下调begin while k+k=n do begin i:=min 2k,2k+1; 如果2k+1不存在直接返回k+k否则返回2个中间的值较小的元素 if stistk then begin swap(i,k); k:=i; end else exit end;end;堆的构造就是不断插入到堆的过程 62351分别插入权为6,2,3,5,1的元素6(1)6(2)26(3)236(4)2356(5)2351堆的插入.删除PROC add(x:longint); 添加一个值为x的元素begin inc(n); stn:=x; u

6、p(n)end;PROC del(x:longint); 删除一个值为x的元素begin an:=ax; down(x)end;思考题1：合并果子在一个果园里，多多已经将所有的果子打了下来，而且按果子的在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，次合并之后，就只

7、剩下一堆了。多多在合并果子时总共消耗的体力等于每次合就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和。并所消耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。多多耗费的体力最少，并输出这个最小的体力耗费值。【数据规模数据规模】对

8、于对于30%的数据，保证有的数据，保证有n=1000;对于对于50%的数据，保证有的数据，保证有n=5000;对于全部的数据，保证有对于全部的数据，保证有nTi而且jCi+1那么根据定理1，将K,i+1替换后肯定更优。于是得到了一个算法的基本流程：1.将任务按照Ti排序。2.从小到大枚举i。维护当前最优方案的集合U。每次将当前的任务I加入U后。如果不满足条件了，那么删去U中耗时最长的任务。3.输出最优方案即可。 因此我们需要使用一种数据结构，它能快速删除耗时最长的任务，同时快速的插入一个新元素。显然，使用大根堆即能满足题目要求。思考题3： juiceJonh正在研制一种有趣的“水杯”： 1）底

9、面是W x H 的相同小方格组成 (3 = W = 300, 3 = H = 300) 2）每个小方格上放置一个底面是1x1的，高度是B(1 = B = 1,000,000,000)的水晶块。 这些水晶块都粘贴在一块，之间不会漏水。John在制成之前，想知道他所要制的这种“水杯”能最多装多少水？juice【样例数据样例数据】4 55 8 7 75 2 1 57 1 7 18 9 6 99 8 9 9【样例输出样例输出】12解释解释：两个高度为1的和一个高度为2的可装水到高度为5；一个高度为6的可装水到高度为7。共装水： 2*4 + 3 + 1 = 12.分析 “木桶效应”：盛水的多少，不在于木

10、桶上那块最长的木板，而在于木桶上最短的那块木板。 因此，我们从“边上”考虑，每次优先处理的是“最短的那块木板”，由于本题中间可能有更高的“块”，可以由外向内地逐步处理，“边”也逐步“加高”。 从外到内初步处理，用小根堆存储读入的数据，每做一次初步累加结果即可。样例分析思考题4：排序 你出了一道信息学竞赛题，就是给n个数排序。输入格式是这样的： 试题有若干组数据。每个数据的第一行是一个整数n，表示总共有n个数待排序；接下来n行，每行一个整数，分别表示这n个待排序的数。 例如右边，就表示有两组数据。第一组有3个数(4,2,-1)，第二组有4个数(1,2,3,4)。数据：342-141234排序 可

11、是现在你做的输入数据出了一些问题。可是现在你做的输入数据出了一些问题。例如右边的数据，按理说第一组数据有例如右边的数据，按理说第一组数据有2个数个数(1,9)，第二组数据有，第二组数据有3个数个数可可是是“3”下面并没有出现三个数，只出现下面并没有出现三个数，只出现了一个数了一个数“2”而已！而已！ 现在你需要对数据进行修改，改动中现在你需要对数据进行修改，改动中“一步一步”的含义是对文件中的某一个数的含义是对文件中的某一个数+1或或-1 写个程序，计算最少需要多少步才能将写个程序，计算最少需要多少步才能将数据改得合法。数据改得合法。数据：21932分析(1) 设f(i)表示要将前i个数改得合法需要的最少步数。 则 f(i)=minf(j)+|A(j+1)-(i-j-1)| 其中1=jI 边界f(1)=A(1) 时间复杂度为O(n2)分析(2) f(i)=minf(j)+|A(j+1)-(i-j-1)| 其中1=j0iA(j+1)+j+1 第二类决策：A(j+1)-(i-j-1)A(j+1)+j+1 如果分开计算f(i)： 对于第一类：f(i)=minf(j)+A(j+1)+j+1-i 对于第二类：f(i)=minf(j)-A(j+1)-j-1-i分析(3) 我们将两类决策分开计算。 随着i的增加，会有一些决策从第一类转到第二类。 我们用两个二叉堆维护两类