哈夫曼树(Huffman Tree)

这篇具有很好参考价值的文章主要介绍了哈夫曼树(Huffman Tree)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

定义

哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

实例引入

现在有这样一个经典问题:果子合并。

现在得到很多果子,需要把这些果子合并成一堆。每一次合并,可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 n−1 次合并之后,就只剩下一堆了。在合并果子时总共消耗的体力等于每次合并所耗体力之和。

假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使耗费的体力最少,并输出这个最小的体力耗费值。

例如有 3 种果子,数目依次为 1,2,9。可以先将 1、2 堆合并,新堆数目为 3,耗费体力为 3。

接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。所以总共耗费体力=3+12=15。可以证明 15 为最小的体力耗费值。

我们把这几个果子看成树的叶子

哈夫曼树(Huffman Tree) 

 然后通过逐次合并其中两个叶子(果子),使根节点的权值最小,根据上面的分析先合并1,2得到3,之后合并3,9得到12。其中我们要计算的便是产生的新节点的权值,把这先权值相加,即是最后要求的体力值。

哈夫曼树(Huffman Tree)

进一步分析可以发现,假设初始状态下我们有四个点,是四个点之间的最优解问题,当我们合并其中两个点之后就变成了三个点的最优解问题,以此类推;而且如果保证每次选的两个数都是最小的(最优的),那么接下来都是最优解的情况了。

由于数据输入是并不是按照从小到大排列,故可以使用小根堆来做。 文章来源地址https://www.toymoban.com/news/detail-473494.html

 代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	priority_queue<int, vector<int>, greater<int>> heap;
	while (n--)
	{
		int x;
		scanf("%d", &x);
		heap.push(x);
	}
	int res = 0;
	while (heap.size() > 1)
	{
		int a = heap.top();
		heap.pop();
		int b = heap.top();
		heap.pop();
		res += a + b;
		heap.push(a + b);
	}
	printf("%d\n", res);
	return 0;
}

到了这里,关于哈夫曼树(Huffman Tree)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】哈夫曼编码(最优二叉树实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(45)
  • 哈夫曼编码(Huffman Coding)原理详解

    哈夫曼编码,又称为哈夫曼编码(Huffman Coding) 是一种 可变长编码 ( VLC, variable length coding))方式,比起定长编码的 ASCII 编码来说,哈夫曼编码能节省很多的空间,因为每一个字符出现的频率不是一致的; 是一种用于 无损数据压缩 的熵编码算法,通常用于压缩重复率比较

    2024年02月03日
    浏览(46)
  • 数据结构 实验17:Huffman树和Huffman编码——学习理解哈夫曼树

    目录 前言 实验要求 算法描述 个人想法 代码实现和思路、知识点讲解 知识点讲解 文件传输 Huffman树的存储 Huffman的构造  Huffman编码 编码和译码 代码实现 文件写入和输出 Huffman树初始化 构造Huffman树 求带权路径长度 Huffman编码 Huffman译码 结束 代码测试 测试结果 利用Huffman编

    2024年02月03日
    浏览(61)
  • 树、二叉树、哈夫曼树、B树、B+树、红黑树相关计算

    树 树中的节点数等于所有节点的度数之和+1(一个节点的孩子个数称为该节点的度) 度为m的树中第i层上至多有 m i − 1 m^{i-1} m i − 1 个节点 高度为h的m叉树至多有 m h − 1 m − 1 frac{m^h-1}{m-1} m − 1 m h − 1 ​ 个节点 具有n个节点的m叉树的最小高度是 ⌈ l o g m ( n ( m − 1 ) + 1

    2024年02月13日
    浏览(43)
  • 15哈夫曼树/哈夫曼编码

    哈夫曼树又称为 最优树 ,作用是找到一种效率最高的判断树。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点之间的路径。 结点的路径长度 :两结点间路径上的分支树 如图 a :从 A - D 的路径长度就是是 2。从 A 到 B C D E F G F I 的路径长度分别为 1 1 2 2 3

    2024年02月05日
    浏览(45)
  • 哈夫曼树、哈夫曼编码/解码

    哈夫曼树的基本介绍 哈夫曼树构建步骤图解 创建哈夫曼树代码实现 基本介绍 哈夫曼编码原理剖析 哈夫曼编码的实例 思路分析 代码实现 使用哈夫曼编码压缩文件的注意事项(代码胜省略)

    2024年02月08日
    浏览(42)
  • 哈夫曼树与哈夫曼编码

    哈夫曼树:结点中赋予一个某种意义的值,称为结点的权值,从根结点开始,到目标结点经过的边数,称为路径长度,路径长度乘以权值,称为带权路径长度; 例如:根结点代表着快递集散点,一个叶子结点权值是5,在业务逻辑中代表着重量是5斤的货物📦,路径长度是3,

    2024年02月05日
    浏览(49)
  • 哈夫曼树详解及其应用(哈夫曼编码)

    一,哈夫曼树的基本概念 路径: 从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径 结点的路径长度 :两结点之间路径上的 分支数 树的路径长度: 从 树根 到每一个结点的 路径长度之和 . 记作:TL 权(weight): 将树中结点赋给一个有着某种含义的数值

    2024年02月04日
    浏览(50)
  • 哈夫曼树、哈夫曼编码和字典树

    目录 哈夫曼树 树的带权路径长度(wpl) 哈夫曼编码 代码实现哈夫曼树 封装哈夫曼树的节点 构建哈夫曼树 字典树 执行流程 代码实现字典树 封装字典树的节点 构建字典树         哈夫曼树(Huffman Tree)是一种带权路径长度最短的二叉树。哈夫曼树常常用于数据压缩,其压

    2023年04月09日
    浏览(51)
  • 哈夫曼树,哈夫曼编码及解码详解

    🌍新人小白的博客 ⌛️希望大家多多关注 🌱一起加油,共同成长 🎃以后会经常更新哒~🙈 ⭐️个人主页: 收藏加关注,永远不迷路~⭐️ 一: 顺序表的操作,你真的学会了吗? 二: 顺序栈的基本操作 三: 循环队列的基本操作,你学会了吗? 四: 单链表的操作(超详细

    2024年02月05日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包