ACM基础（四）：树之Huffman Coding哈夫曼（霍夫曼）编码

本文主要是介绍ACM基础（四）：树之Huffman Coding哈夫曼（霍夫曼）编码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

一、原理
二、伪代码

一、原理

频率：

在这里插入图片描述

原理：

构造的方法就是将所有的指令按使用的频度（也就是程序中出现的概率）由小到大依次排列，每次将两个使用频度最小合并在一起，构成一个频度为两者之和的新结点，将其与余下的结点放在一起。接着再从这些结点中继续找两个使用频度最小合并在一起，构成一个频度为两者之和的新结点。重复上述过程，全部结点合并完成。

在这里插入图片描述

过程：

0.01和0.02是目前最小的，结合为0.03
0.03和0.03是目前最小的，结合为0.06
0.06和0.06是目前最小的，结合为0.12
0.07和0.07是目前最小的，结合为0.14

…

二、伪代码

HUFFMAN()// 共有n个数n ← |C|// 优先级队列（谁小谁在队首）Q ← C// n个数有n-1对for i ← 1 to n-1// 分配一个新的结点，联合两个最小结点do	allocate a new node z// 新结点的左孩子就是弹出的一个最小队首left-son[z] ← x ← EXTRACT-MIN(Q)// 新结点的右孩子就是弹出的一个最小队首right-son[z] ← y ← EXTRACT-MIN(Q)// 新结点的频率就是两子节点频率之和f[z] ← f[x] + f[y]// 将新结点插入到优先级队列中INSERT(Q, z)// 返回树根return EEXTRACT-MIN(Q)