贪心算法 --- 例题2.哈夫曼编码问题
2021/11/28 11:10:13
本文主要是介绍贪心算法 --- 例题2.哈夫曼编码问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
贪心算法 — 例题2.哈夫曼编码问题
一.问题描述
Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。
树的带权路径长度:树中所有叶子结点的带权路径长度之和,通常记作:WPL = Σwi*li (i=1~n)
哈夫曼树,Huffman树定义:在权为w1,w2,…,wn的n个叶子结点的所有二叉树中,带权路径长度WPL最小的二叉树称为赫夫曼树或最优二叉树。
本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。
二.解题思路
哈夫曼树的构造(哈夫曼算法)
- 1.根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
- 2.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
- 3.在F中删除这两棵树,同时将新的二叉树加入F中.
- 4.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)
代码如下:
// 哈夫曼编码贪心算法实现 // 输入格式 // 输入的第一行包含一个正整数n(n<=100)。 // 接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。 // 输出格式 // 输出用这些数构造Huffman树的总费用。 #include<bits/stdc++.h> using namespace std; int Huffman(int *a, int n) { int ans = 0; int pos = 0; int temp_n = n; while(n>1) { // sort(a+pos, a+temp_n); sort(a, a+temp_n); ans = ans + (a[pos] + a[pos+1]); a[pos+1] = a[pos] + a[pos+1]; pos++; n--; } return ans; } int Huffman2(int a[], int n) { int ans = 0; sort(a, a+n); for(int i=0; i<n-1; i++) { ans += (a[i]+a[i+1]); a[i+1] += a[i]; sort(a, a+n); } return ans; } int main() { int t, n; cin>>t; while (t--) { cin>>n; int a[n]; for(int i=0; i<n; i++) cin>>a[i]; cout<<Huffman2(a, n)<<endl; } system("pause"); return 0; }
参考毕方明老师《算法设计与分析》课件.
欢迎大家访问个人博客网站—乔治的编程小屋,和我一起为大厂offer努力!
这篇关于贪心算法 --- 例题2.哈夫曼编码问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南