石子合并：压缩之外，同一个 Huffman
暂且放下前面几页讨论的压缩，看一个表面无关的问题：有若干堆石子，每次合并任意两堆，代价等于两堆石子数之和，合到只剩一堆。如何安排合并顺序，使总代价最小？
关键观察： 这和 Huffman 建树是同一个算法。把每堆石子数当作叶子的 weight，每次合并产生一个内部 node（weight = 两子之和，正好是这步的代价）。总代价 = 所有内部 node weight 之和 = ∑（每堆石子数 × 它被合并的次数）= ∑（weight × 深度）。最小化它的 greedy，就是每次合并最小的两堆——与动手建树一页完全一致。
下面动手验证。可以切换 greedy 策略：最小优先（Huffman 最优）对照最大优先（刻意选取较差的方案），观察同一组石子两种顺序的总代价相差多少。点「下一步」逐次合并。
为什么「最小优先」最优？ 直觉和压缩一样：越早被合并的堆，会被后续每一次合并重复计入代价（它在树里越深、被累加越多次）。所以要让小的堆沉到底、大的堆晚点进来、靠近根——这正是 Huffman 让低频字符 codeword 长、高频字符 codeword 短的同一笔账。
1 · 这类问题还会以多种形式出现
同一个「optimal merge / 最小化加权路径」内核，在算法题与工程里反复出现：
- 连接绳子的最小费用 / 合并果子——字面上就是本页。
- 外部排序的多路归并——k 个有序段如何两两归并，使总搬运量最小。
- 文件 / 数据块的最优拼接顺序——每次拼接代价正比于已拼长度。
它们都能映射到「带权叶子 → 最小加权外部路径长度的二叉树」，于是答案都是 Huffman 那个 greedy。压缩只是这一族问题里最为人熟知的一种。hierarchical softmax一页是它在神经网络中的另一种形式。