← Huffman 编码树 · 拆解 huffman coding / 动手建树:每次合并两个最小 待审核 2 / 6
algorithm · 单步建树

动手建树:每次合并两个最小

Huffman 建树是一个简洁的 greedy 过程,只有一条规则,反复做到只剩一个为止:

  1. 把每个字符做成一个 node,frequency 作为 weight,全部放进一个 priority queue。
  2. 取出 weight 最小的两个,新建一个父 node(weight = 两者之和),把它俩挂为左 / 右孩子。
  3. 把这个父 node 放回 priority queue。
  4. 回到第二步,直到 priority queue 里只剩一个 node——它就是树根。

直觉:最罕见的两个字符最先被合并,于是它们离根最远、codeword 最长;frequency 高的 node 很晚才并进来,离根近、codeword 短。改下面的「源文本」即可换输入——每次改动,页面都用构建期插桩产出的同一个函数在浏览器里原生跑一遍,现算出这一版的每一步快照:既不含解释器,也不重新解析代码,用户只提供数据、不提供可执行代码。

1 · 建完之后:读出 code table

树建好后,从根走到每个叶子,向左记 0、向右记 1,一路收集到的 0/1 串就是那个字符的 codeword。叶子越深 → codeword 越长 → 对应字符越罕见,这正是我们想要的(建树完成后,code table 即列在上方 lab 内)。

tie-break 要稳定: 当多个 node weight 相同,取哪两个其实有自由度,会得到形状不同但总长相同的树。本 demo 固定「weight 相同则先进 priority queue 者优先」,保证每次结果一致、便于对照——实际格式里(见应用实例)也会用一套确定的规则消除这种歧义。