堆与并查集讲解.ppt

“ ” 堆与并查集 * * /vjudge/contest/view.action?cid=83472#overview Vjudge CONTEST: 早起的蛤蛤有虫吃2 密码：bslyexscs EXERCISES 补充知识 树： 一对多的数据关系 一个点可以有多个后继 但是只有一个前驱 二叉树 的存储方式 顺序存储 用数组来存储所有节点信息 A B I C F G L D E G H K -1 -1 -1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -1 特殊的二叉树 满二叉树 深度为K且节点总数为2K-1 完全二叉树 树中所含的 N 个结点和满二叉树中编号为 1 至 N 的结点一一对应。 R2I 是 RI 的左孩子； R2I+1 是 RI 的右孩子 堆 定义（以大根堆为例） 大根堆是一棵完全二叉树，且满足任意一个节点的值大于其儿子的值，即HEAP[I]HEAP[I*2] HEAP[I]HEAD[I*2+1] 小根堆与大根堆类似 堆的基本操作--插入元素 对于一个已经建好的堆，插入元素且使得仍旧是一个堆 12 98 73 56 64 36 27 49 40 55 堆：R[10]{98, 64, 56, 55, 36, 27, 49, 40,12} 36 73 73 64 代码 INSERT（INT A） { HEAP[N] = A; FOR(INT I=N; I1HEAP[I/2]HEAP[I]; I/=2) SWAP(HEAP[I],HEAP[I/2]); N++; } 堆的调整 假设H.R[S..M]中记录的关键字除 R[S] 之外均满足堆的特征 12 73 56 64 36 27 49 40 55 73 Re = 12 64 12 55 代码 VOID HEAPADJUST(INT S,INT T) { INT RE = HEAP[S]; FOR(INT J=2*S; J=T; J*=2) { IF(J+1=T HEAP[J+1]HEAP[J]) J++; IF(RE = HEAP[J]) BREAK; HEAP[S] = HEAP[J];S = J; } HEAP[S] = RE; } 删除元素 要删除某个元素，我们只需要将这一元素与最后一个元素互换，调用一次HEAPADJUST()函数就可以了 建堆 1.重复调用N次INSERT函数 2.从第N/2个节点开始，重复调用HEAPADJUST函数，直到处理到第一个节点 堆与优先队列 优先队列 在队列头的始终是最大（最小）的元素 新元素入优先队列 INSERT（）； 删除对头元素 SWAP（FRONT，END）； HEAPADJUST（）； 例题：合并果子 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 　　每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 　　因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 　　例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 首先，合并的总代价相当于 M(1)*果子数(1) +M(2)*果子数(2) + . . . +M(N)*果子数(N)? 所以我们只需要使果子数大的那一堆的M尽量小，使果子数小的那一堆的M尽量大一种简单的策略就是每次取两个最小的堆，合并 * * 1.排序 2.依次取出重量最小的两堆果子合并成为一堆，将这一堆加入到全部的堆里面 * * 并查集 并查集是一种树型的数据结构，用于处理一些不相交集合（DISJOINT SETS）的合并及查询问题。 例子 亲戚(RELATIONS) 　　若某个家族人员过于庞大，要判断两个是否是亲戚，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 　　规定：X和Y是亲戚，Y和Z是亲戚，那么X和Z也是亲戚。如果X,Y是亲戚，那么X的亲戚都是Y的亲戚，Y的亲戚也都是X的亲戚。 基本操作 UNIONSET(X, Y)：把元素 X 和元素 Y 所在的集合合并，要求 X 和 Y 所在的集合不相交，如果相交则不合并。 FIND(X)