哈夫曼编码，这东西听起来挺高深，实际上就在脑子里打个比方就懂了。想象你手里有一堆不同形状、大小的石头，你要把它们装进一个行李箱里。
要是所有石头都一样大，那如何办？直接记个数字，大小一样记成 1 或 2，忒费事了。但你手里的石头不一样，有的大有的小，大的务必占两个箱子，小一点的占一个箱子。为了省力气，你会尽量把两个最大的石头放在一起，这样那个最大的箱子不用多占两个，就只占一个？对，这就叫贪心算法，哈夫曼编码就是如此“凑”出来的。 别被名字误导了，它不是把频率加起来，也不是把数值相加。哈夫曼编码是给那些频率小的字符分配更长的代码，给频率大的字符分配更短的代码。
为啥？出于大字符出现的概率高，码字短省下的传输工夫才最划算。假设有四个字母，A、B、C、D。
要是它们出现的机会一样多，那每位的编码长度根本固定，这没啥区别。但现实情况是，A 可能天天出现，B 一天出现一次，C 半天，D 半夜。
这时候，要是都给一个固定的 2 位码，A 和 B 别看占用长度一样，但 B 要浪费 1 位去区分，A 就把这局部浪费了。哈夫曼编码就是把 B 这个“低频”的字符，强行塞进一组 3 位的码字里，而让 A 这个“高频”字符，只用 2 位的码字。
看似 B 长，但实际传输里，它占据的那一串 10101（假设），长度才 5 个单位，而 A 的 010 只是 3 个单位。省下来的 2 个单位，就是给高频字符赚回来的。 具体如何算，大家可能都见过那种“二叉树”的画法，别急，不用画复杂的图，就用那个“凑数”的思路来推。拿三个数字代表四个字符，频率分别是 10、20、30、40。
第一步，找出最小的两个数，也就是 10 和 20，把它们合并成一个新节点（比如叫节点 X），这个新节点代表的频率就是 30。
这时候树的结构就变了，X 和 40 还是分开的父子关系，哪位大哪位亲。
第二步，目前树里剩下 X(30) 和 40 两个主要分支。
这时候，最小的两个数又是 30 和 40 了，把它们合并，拿到一个新节点 Y，频率就是 70。
第三步，整个树就建成了。根节点是 70，它的儿子是 Y(70) 和 X(30)。Y 的左孩子是 X，右孩子是 40。X 的左孩子是原 10，右是原 20。
你看，这里有个细节，原 10 和原 20 在 X 的左右两边，这意味着它们到根节点的路径长度不一样，一个多一步，一个少一步。路径长就代表编码长。 举个例子，假设你是做跨境电商的，客户喜爱大包装的包裹，小包装的包裹极少。
要么假设你是做输入法，英文字母里 "E" 出现频率极高，"G" 相对少一点。目前你要给这些字母编 Huffman 码。先算频率，E 最高，G 次之，然后 Z、Q、A、B 频率依次递减。你会发现，频率最高的几个字符，在树的结构里往往就是处于叶子节点的浅层，也就是离根节点比较近。离得近，树的路径短，编码自然就短。而频率低的那个字符，哪怕树再大，只要它平时不常出现，它距离根节点的路径就会比较远，编码长度就多了。
这就终止了吗？还没完。 再深入一点，哈夫曼编码的字典序难题实际上挺费事，要是按字母表顺序，像 A、B、C 这些顺序固定的字符，编码长度往往是不变的，这就丧失了优化的意义。哈夫曼编码算出来的树，它的根节点有两个儿子，左子树和右子树。你能够规定，子树的左分支代表 0，右分支代表 1。
这样，左边的字符编码长度一般比右边的少，要么按照某种顺序排列。但这只是约定俗成，哈夫曼编码本身并不规定左右哪位代表 0。你能够自己定，左代表 1，右代表 0，这不影响编码长度和效果。
不过反过来想，要是让你按频率排序，把高频字符放左边，低频字符放右边，是不是更直观？自然能够了。高频字符在左边，编码短；低频字符在右边，编码长。
这样读起来就顺口，逻辑也顺畅，不好办出错。 有人可能会问，那要是有字符三种如何办？哈夫曼编码算法对节点数量的限制是没有的。
你想想，三种频率的字符，先合并最小的两个，然后跟最大的合并，最终再合并剩下的。
这个过程在二叉树上就表现为叶子节点有三个。
这时候，根节点有三个儿子，每个儿子对应一个叶子节点。
这三个叶子节点在树里的位置，距离根节点的路径长度自然不同。频率最高的那个，路径最短；频率最低的那个，路径最长。你就连能够构造一种特殊情况，所有字符的编码都相同，只要知足编码唯一性即可，但这在哈夫曼编码里极少见，出于那样就浪费了编码长度。哈夫曼编码的优势就在于它能让频率最小的那些不常出现的字符，尽量多地合并，进而推大编码长度，达到最优解。 最终还得提一下，哈夫曼编码是一种前缀码。代码里绝对不要出现“祖父是 0，父是 0，那是 00"这种结构，否则解码时就会歧义。
比如 101 和 100 与此同时出现，解码器不知道该先取 1 还是先取 10。哈夫曼编码生成的树，天然知足前缀特性，左边的子树里不可能出现右子树的编码，右边的子树里也不可能出现左子树的编码。
这是算法设计的一个隐形优点，保证了解码过程好办可靠，不会陷入死循环。 故此说，哈夫曼编码就是给那个复杂的概率分布，量身定做了一套编码方案。它不需求你懂啥复杂的数学公式，也不用纠结字典序，只需求记住一个核心：高频者短频者长。通过不断合并，直到只剩下一个节点，在这个过程中，高频字符离根节点越近，编码就越短。对于工程师来说，这可能意味着更少的比特传输，更节省的线路成本；对于人类来说，可能意味着更少的记忆负担，更自然的语言习惯。就如此好办，关键在于把“频率小”和“路径长”这两个看似矛盾的东西，通过树的结构巧妙结合在了一起。
