ZCMU OJ 1810: Huffman树

简介：
本题要求设计并实现Huffman树的构建及其编码算法。通过给定字符及相应频率，生成最优前缀码，最小化数据存储空间，适用于信息压缩领域。 题目描述 在编码领域内，Huffman树有着广泛的应用价值。本题着重探讨的是构建Huffman树的过程。 给定一个数列{pi}={p0, p1,..., pn-1}，利用该序列构造Huffman树的具体步骤如下： 首先，在数列中找到最小的两个数值pa和pb，并将这两个值从原数组中移除。随后，它们的总和被添加回这个集合中。此操作所消耗的成本即为 pa + pb。 重复上述过程直至整个集合仅剩下一个元素为止。 在整个构建过程中，所有步骤产生的费用相加，则构成了构造Huffman树所需的总体成本。 对于给定序列{pi}={5, 3, 8, 2, 9}， 具体操作如下： 第一步：在数列中找到最小的两个数值为2和3。将它们从原数组移除，并加入总和5，得到新的集合{5, 8, 9, 5}，此时产生的费用是5。 第二步：继续寻找当前序列中的最小值，即再次选择两个数字5与另一个5作为操作对象，删除这两个数并将10添加回集合中。