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、空间复杂度空间复杂度是对⼀个算法在运行过程中临时占用存储空间大小的量度。⼀个算法在计算机存储器上所占用的存储空间包括存储算法本身所占用的存储空间算法的输⼊输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
