ot->left) { st +='0'; } print_Code(proot->left, st); if(!proot->left && !proot->right)//叶子 { printf("%c's code:", proot->key); for(size_t i=0; i
right) st+='1'; print_Code(proot->right, st); } //清空堆上分配的内存空间 void del(Tree *proot) { if(proot == nullptr) return ; del(proot->left); del(proot->right); delete proot; } // 霍夫曼编码 void huffman() { int i; char c; int fr; // 读入测试数据 for(i=0; i
key = c; pt->freq = fr; pque.push(pt); } //将森林中最小的两个频度组成树，放回森林。直到森林中只有一棵树。 while(pque.size()>1) { Tree *proot = new Tree; pTree pl,pr; pl = pque.top(); pque.pop(); pr = pque.top(); pque.pop(); proot->freq = pl->freq + pr->freq; proot->left = pl; proot->right = pr; pque.push(proot); } string s; print_Code(pque.top(), s); del(pque.top()); } int main() { //freopen("in.txt", "r", stdin); huffman(); return 0; }
输入为：
a 45
b 13
c 12
d 16
e 9
f 5
输出：
对应的二叉树为：
算法以freq为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，
其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树proot。算法huffman用最
小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的节点删除、插入均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。
因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn) 。
参考资料：
《算法导论》