数据结构中的 t 元树霍夫曼算法

一项简单的算法

  • 准备一个包含 n 个初始霍夫曼树的集合，其中每一个都是一个单叶节点。按权重（频率）将 n 棵树保留在优先级队列中。
  • 移除或删除前两棵树（权重最小的树）。将这两棵树组合起来创建一个新树，其根节点与两棵树相关联作为子树，且其权重是这两个子树权重之和。
  • 将这棵新树保存在优先级队列中。
  • 重复步骤 2-3，直到所有部分霍夫曼树都合并到一棵树中为止。

这是一个贪心算法：每次迭代时，该算法进行一个“贪婪”决策，合并具有最小权重的两个子树。算法有可能提供所需的结果吗？

  • 引理：令 x 和 y 是两个出现频率最低的字符。存在一个最佳编码树，其中 x 和 y 是有着最小深度的兄弟节点，与树中的其他叶节点相同。
  • 定理：霍夫曼编码被视为最佳无前缀二进制编码（对于给定的字母集，贪心算法构造霍夫曼树，最小化外部路径权重）。

更新于： 2020 年 7 月 1 日

467 人次浏览

开启您的 职业之旅

完成本课程可获得认证

开始
广告