构建哈夫曼树时存在多个相同最小权值节点的合并选择问题

结论 #

前两种合并操作符合哈夫曼树构建规则，第三种不符合。

判定依据 #

二叉哈夫曼树的构建逻辑没有歧义，核心要求非常明确：每一轮合并必须从当前所有待合并的根节点（包含原始叶子节点、之前合并生成的父节点）中，选出两个权值最小的节点合并为新父节点，新节点权值为两个子节点权值之和；合并完成后将两个原子节点从待合并集合移除，新节点放回集合，重复操作直到集合内仅剩一个节点。
回到本次构建场景：
第一步合并完权值为1的D、E节点，得到权值为2的DE节点后，待合并集合内共有4个根节点，权值分别为A(4)、B(2)、C(2)、DE(2)。此时集合内的最小权值为2，共有3个权值为2的节点，因此本轮合并只要选择两个权值为2的节点配对就符合规则，合并出的新节点权值必然为2+2=4。

• 第一种方案合并DE(2)和B(2)，新节点权值为4，完全符合规则。
• 第二种方案合并DE(2)和C(2)，新节点权值为4，完全符合规则。
• 第三种方案给出的结构根节点权值为6，是4+2的计算结果，说明该操作选择了一个权值为4的节点和一个权值为2的节点配对，跳过了其他权值为2的最小节点，直接违反了“每次选两个最小权值节点合并”的硬性要求，是错误的。

补充说明：第二轮如果选择两个原始节点B(2)、C(2)合并本身是合法操作，合并出的新节点权值也应为4，结构为根节点下挂B、C两个子节点，但题目给出的第三种结构并不是该合法操作对应的结果，属于错误的跨步骤合并产物。

内容的提问来源于stack exchange，提问作者bruh