最佳归并树

http://data.biancheng.net/view/79.html

---

数字代表段的长度，带权路径长度与硬盘读取开销成正比

上图中的归并过程需要对外存进行读/写的次数为：（9+30+12+18+3+17+2+6+24）*2*2=484（图中涉及到了两次归并，对外存的读和写各进行 2 次）

对于如何减少访问外存的次数的问题，就等同于考虑如何使 k-路归并所构成的 k 叉树的带权路径长度最短。

构造一棵赫夫曼树作为归并树：

image.png

(2*3+3*3+6*3+9*2+12*2+17*2+18*2+24*2+30)*2=446

---

附加“虚段”的归并树

若 9 个初始归并段改为 8 个，在做 3-路平衡归并的时候就需要有一个结点的度为 2。

image.png

• 注意：虚段的设置只是为了方便构建赫夫曼树，在构建完成后虚段自动去掉即可。

对于如何判断是否需要增加虚段，以及增加多少虚段的问题，有以下结论直接套用即可：

在一般情况下，对于 k–路平衡归并来说，若 (m-1)MOD(k-1)=0，则不需要增加虚段；否则需附加 k-(m-1)MOD(k-1)-1 个虚段。