代码与动画 HUFFMAN CODING
哈夫曼编码.
反复合并频次最小的两棵树，沿树的左右分支生成前缀编码。
排序选最小：O(n² log n)空间 O(n)可变长前缀编码
原理与执行逻辑
以字符频次为叶权重，每次合并最小的两棵候选树。由根到叶读取左右分支的 0、1 标签，生成总加权编码长度最小的前缀编码。
执行步骤
- 为每个字符建立一棵只有叶节点的树。
- 将候选按权重排序，取出最小的两棵。
- 创建权重等于两者之和的父节点，将合并树放回候选集。
- 剩一棵树后遍历，左分支追加 0、右分支追加 1，输出每个字符编码。
关键理解
字符都在叶节点，因此一个字符编码不会成为另一个的前缀。每次合并会令子树全部叶子的码长增加 1，成本恰好是两棵子树权重之和。
简短示例
A:2、B:3、C:7 先合并 A 与 B 为 5，再与 C 合并。可得到 A=00、B=01、C=1，总加权位数为 2×2 + 3×2 + 7×1 = 17。
代码与执行动画
STEP 0 / 14function huffman(entries) { let serial = 0; const queue = entries.map(([symbol, weight]) => ({symbol, weight, order: serial++})); while (queue.length > 1) { queue.sort((a, b) => a.weight - b.weight || a.order - b.order); const left = queue.shift(), right = queue.shift(); queue.push({weight: left.weight + right.weight, left, right, order: serial++}); } const codes = {}; function visit(node, prefix) { if (node.symbol !== undefined) { codes[node.symbol] = prefix || '0'; return; } visit(node.left, prefix + '0'); visit(node.right, prefix + '1'); } visit(queue[0], ''); return codes;}候选树 5
当前数据正在操作已访问 / 命中标记 / 指针
0
初始化字符树
每个字符独立成树，节点值是出现频次。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
哈夫曼编码的操作规则
本演示每轮对候选树排序，左边标 0，右边标 1。相同频次按创建顺序选择；单字符编码约定为 0。输出编码与总加权位数。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
免费关联练习：反复合并最小的两个权重，与哈夫曼建树使用同一贪心过程；题目求总代价，不要求输出字符编码。
同类最优合并问题；力扣会员题，求合并成本，不要求输出哈夫曼编码。