1、堆通常分为两种类型：
- 大顶堆：根结点的值必须大于它孩子结点的值
- 小顶堆：根结点的值必须小于它孩子结点的值
结点的路径长度：从根结点到该结点的路径上的连接数
树的路径长度：树的每个叶子结点的路径长度之和
结点的带权路径长度：结点的路径长度与结点权值的乘积
树的带权路径长度（WPL）：树的所有叶子结点的带权路径长度之和
2、哈夫曼树的构造过程，
森林中选出两个结点权值最小的⼆叉树,合并这两个⼆叉树，增加⼀个新的结点作为新的⼆叉树的根，权值为左右孩子的权值之和。
3、哈夫曼编码
3.1、定长编码
每个字符的编码长度是一样的，缺点是浪费空间。
3.2、变长编码
单个编码的长度不一样，出现频率越高的编码长度越短。变长编码可以将短编码赋予平均出现频率较高的字符，同⼀消息的编码长度小于定长编码。
3.3、前缀码
前缀码就是没有任何码字是其他码字的前缀。
4、哈夫曼树
特征：
- 每片叶子结点都包含⼀个字符；从结点到其左孩子的路径上标记0；从结点到其右孩子的路径上标记1
- 编码均具有前缀属性
- 从根结点到包含字符的叶子结点的路径上获得的叶结点的编码
5、复杂度分析
⼀个算法的好坏，我们可以从时间和空间两个维度去衡量。执行时间越短，占⽤内
存空间越小的算法，我们认为是更优的算法。
好算法的标准：⾸先它必须能彻底解决这个问题（称为准确性），且根据其编写出的程序在任何情况下都不能崩溃（称为健壮性）。
算法的时间复杂度反映了程序执行时间随输⼊规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。
5.1、时间复杂度
⼀个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。记作T(n)=Ｏ(f(n)),称Ｏ(f(n))
为算法的渐进时间复杂度，简称时间复杂度。
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
5.2、空间复杂度
空间复杂度是对⼀个算法在运行过程中临时占用存储空间大小的量度。⼀个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输⼊输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
