贪心算法：赫夫曼编码

前缀码 ，即没有任何码字是其他码字的前缀。且前缀码确实可以保证达到最优数据压缩率。

二进制字符码的编码过程都简单，只要将表示每个字符的码字连接起来即可。前缀码的作用是简化解码过程，由于没有任何码字是其他码字的前缀 i，编码文件的开始码字是无意义的。我们简单的就能识别开始码字并转换回原字符。

解码过程需要前缀码的一种方便的表示形式，以便我们可以容易地截取开始码字。二叉树可以满足这种需求，其叶结点为给定的字符。一个字符的二进制码字用从根节点到叶结点的简单路径表示，其中 0 意味着转向左孩子，1意味着转向右孩子。如下图所示，a对应定长编码，b对应变长编码。文件的最优编码方案总是会对应一棵满二叉树。

赫夫曼设计了一个贪心算法来构造最优前缀码，被成为 赫夫曼编码 。

在下面的伪代码中，假定 C 是一个 n 个字符的集合，而其中每个字符 c ∈ C 都是一个对象，其属性 c.freq 表示字符出现的频率，算法自底向上构造出对应最优编码的二叉树。算法使用一个以 freq 为关键字的优先队列Q，以识别两个最低频率的对象将其合并，从|C|个叶结点开始，执行|C|-1 个合并构造出最终的二叉树。

    n = |C|
    Q = C
    for i = 1 to n - 1
        allocate a new node z
        z.left = x = EXTRACT-MIN(Q)
        z.right = y = EXTRACT-MIN(Q)
        z.freq = x.freq + y.freq
        INSERT(Q, z)
    return EXTRACT-MIN(Q)       //返回树的根结点

第二行用 C 中的字符初始化优先队列 C，具体执行过程如下图所示：

赫夫曼编码算法本身倒不算复杂，但是实现起来就有些麻烦了，因为使用混合使用了两种数据结构-–—优先队列和二叉树。用 C 语言使用算法导论第六章中用数组实现的优先队列很难将赫夫曼编码实现。这一点亲身体验……不过找到了一篇外国的关于赫夫曼编码的文章。

他使用了三个数据结构，优先队列、二叉数、码字链表，其中优先队列是用链表实现的，并且将树的结点存储到优先队列中。作者在文章最后给出了完整的基于 C99 标准的 C 语言代码。注释也很全，我将其中的英文注释翻译为了中文(渣英语见谅)，下载链接见下。

源代码下载

自己写了一个其程序流程图如下：

（图片丢失）

赫夫曼编码、解码运行结果：

（图片丢失）