第十章外部排序

第十章外部排序内容摘要：

5 6 调整败者树的方法 : 将新补充的结点与其双亲结点比较 , 败者留在该双亲结点 ,胜者继续向上直至树根的双亲 以在 b[4]补充 15为例 15 4与 3比较 4与 2比较 4 2与 5比较 2 5 调整败者树的方法 7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6 [k路归并对内存的要求 ] 至少要有 k个输入缓冲区和一个输出缓冲区 建败者树的过程 7 1 初始化败者树调整 b[6] 6 调整 b[5] 5 调整 44 调整 334 调整 22 调整 11 2 4 调整 005 4 建败者树的过程 [数据结构 ] (依据：败者树为完全二叉树 )  主： b[0.. k] b[0.. k1]—— k个叶结点 ，存放 k个输入归并段中当前 参加归并的记录（缓冲区） b[k]—— 虚拟记录，该关键字取可能的最小值 minkey  辅： ls[0.. k1] —— 不含叶结点的败者树 存放最后胜出的编号（ ls[0]）以及所记录的败者编号 [处理步骤 ]  建败者树 ls[0.. k1]  重复下列操作直至 k路归并完毕  将 b[ls[0]]写至输出归并段  补充记录 (某归并段变空时 ,补 )，调整败者树 多路平衡归并算法 算法描述：建立败者树 void CreateLoserTree() { b[k] = MINKEY。 for (i = 0。 i k。 i++) ls[i] = k。 for (i = k 1。 i = 0。 i++) Adjust(i)。 } void Adjust(int s) { for (t = (s + k) / 2。 t 0。 t /= 2) { if (b[s] b[ls[t]]) s  ls[t]。 } ls[0] = s。 } 算法描述 : K路合并 void K_Merge() { for (i = 0。 i k。 i++) input(i)。 /* 第 i路输入一个元素到 b[i] */ CreateLoserTree(ls)。 while (b[ls[0]] != MAXKEY) { q = ls[0]。 output(b[q])。 input(q)。