哈夫曼编码（Java）

Huffman编码算法实际上是一个贪心算法

每个字符都是二叉树的叶子结点，非叶子结点则不代表任何字符

有一组字符集{c1, c2, …, cn}，字符集对应的权重{w1, w2, …, wn}

哈夫曼二叉树构建算法：

1. 将字符集和权重构造成结点形成最小堆结点集S，
2. 每次都从最小堆结点集S中选出权重值最小的两个结点x和y作为子节点进行建树，
3. 为这两个子结点构造一个父节点，父节点不保存任何字符，父节点的权重为两个子节点权重之和，
4. 将取出的两个子节点从集合S中移走，将父节点加入S中。
5. 不断循环步骤2,3,4一直迭代下去，直到节点集合S只剩一个结点时，这个结点就是树的根节点。

这样我们就得到了一棵Huffman树，整个过程就是一个自底向上的建树过程。由于从根节点到每个叶子节点有且仅有一条路径，所以，每个叶子的路径都是不一样的，唯一的。我们把从根节点到叶子节点的路径记录下来，便可作为叶子节点上字符的编码。

哈夫曼编码算法：

在哈夫曼树中初始化编码为空，从根节点开始，往左走则编码加0，往右走则编码加1

哈夫曼树的定义代码实现：

public class HuffmanNode implements Comparable {
    protected int key;              // 权值
    protected HuffmanNode left;     // 左孩子
    protected HuffmanNode right;    // 右孩子
    protected HuffmanNode parent;   // 父结点

    protected HuffmanNode(int key, HuffmanNode left, HuffmanNode right, HuffmanNode parent) {
        this.key = key;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

构造哈夫曼树代码实现：

用堆来实现节点集合的存储！

public Huffman(int a[]) {

    private HuffmanNode mRoot;
    HuffmanNode parent = null;
    MinHeap heap;

    // 利用数组a建立最小堆
    heap = new MinHeap(a);

    for(int i=0; i<a.length-1; i++) {   
        HuffmanNode left = heap.dumpFromMinimum();  // 最小节点是左孩子
        HuffmanNode right = heap.dumpFromMinimum(); // 其次才是右孩子

        // 新建parent节点，左右孩子分别是left/right；
        // parent的大小是左右孩子之和
        parent = new HuffmanNode(left.key+right.key, left, right, null);
        left.parent = parent;
        right.parent = parent;

        // 将parent节点数据拷贝到"最小堆"中
        heap.insert(parent);
    }

    mRoot = parent;

    // 销毁最小堆
    heap.destroy();
}

补充知识点：

最小堆：一种经过排序的完全二叉树，其中任一非叶节点的数据值均不大于其左子节点和右子节点的值。

待续！

参考文献：

[1] 【贪心算法】Huffman编码
[2] 哈夫曼树(三)之 Java详解
[3] 详细图解哈夫曼Huffman编码树
[4] 百度百科——最小堆