题目

设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：

(1) 给出完整的合并过程，并求出最坏情况下比较的总次数。

(2) 根据你的合并过程，描述 N（N ≥ 2）个不等长升序表的合并策略，并说明理由。

解析

预备：合并两个有序表的最坏比较次数

合并长度分别为 a、b 的两个升序表（归并步），最坏情况下比较次数 = a + b − 1（最后一个元素无需比较即可放入位置）。总比较次数 = 各次合并的代价之和。

要让总和最小，本质就是「构造一棵 N 个叶子的合并树（每片叶子是初始表），让"加权路径长度（WPL）"最小」——这正是哈夫曼树的目标，权值就是各表的长度。

(1) 6 个表的合并过程与最坏比较次数

答案：按哈夫曼策略每轮合并当前最短两个表，最坏总比较次数 = 825 次。

逐轮模拟（粗体为本轮选出的最短两个）：

轮	当前各表长度	选中合并	合并后表长	本次最坏比较
1	10, 35, 40, 50, 60, 200	10 + 35	45	10 + 35 − 1 = 44
2	40, 45, 50, 60, 200	40 + 45	85	40 + 45 − 1 = 84
3	50, 60, 85, 200	50 + 60	110	50 + 60 − 1 = 109
4	85, 110, 200	85 + 110	195	85 + 110 − 1 = 194
5	195, 200	195 + 200	395	195 + 200 − 1 = 394

总比较次数 = 44 + 84 + 109 + 194 + 394 = 825 次。

编者注（生僻术语）：部分教材把单次合并的代价简化记作 a + b（忽略 −1），按该口径总和会算成 45 + 85 + 110 + 195 + 395 = 830。考研标准答案两种口径都接受，关键是策略正确（哈夫曼合并）+ 中间过程清晰。

(2) N 个不等长升序表的合并策略

策略：每次从当前所有有序表中挑出最短的两个进行合并，直到只剩一个表。等价于以各表长度为权值构造一棵 N 个叶子的哈夫曼树，按"自底向上"方式合并。

为什么这是最优的？

• 把每次合并视为合并树中一个内部结点：它的两个孩子是被合并的两个子表，该内部结点的"代价"= 左右子表长度之和（即被合并产生的新表长）；
• 总比较次数 = 所有内部结点代价之和 ≈ 所有叶子的（长度 × 该叶子在合并树中的深度）之和 = WPL（带权路径长度）；
• 哈夫曼算法（每次合并权值最小两棵子树）保证 WPL 最小——这是哈夫曼定理的直接应用。

直观理解：长表越早卷入合并，其每个元素就在后续合并中被搬动越多次（贡献到的内部结点越多）。最优策略是让长表"最后参与"、短表"最早合并掉"，正好对应"每次选最短的两个"。

实现要点：用小根堆维护当前所有表长。每次 pop 两个最小值 a、b，push a+b 回去，统计 a+b−1 次比较；重复 N−1 次。整体复杂度 O(N log N)。