Skip to main content

霍夫曼树

参考资料​

例题​

洛谷 B2168 【模板】哈夫曼编码

给定 nn 个不同的单词及其出现的频次，请你构造一种哈夫曼编码（Huffman Coding）方案。

哈夫曼编码是一种可变长前缀编码，它通过构建哈夫曼树来实现，使得所有单词的编码长度与其频次的乘积之和（即带权路径长度，WPL）最小。在哈夫曼树中，左分支通常代表 00，右分支通常代表 11。

由于构建哈夫曼树时，对于权值相同的节点合并顺序不同，以及左右子树的分配不同，可能会产生多种满足条件的编码方案。本题只需输出任意一种合法的哈夫曼编码方案即可。输出的单词顺序应与输入顺序保持一致。

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=2005;
string s[N],ans[N];
int ls[N],rs[N];
void dfs(int u,string t="")
{
	if(!ls[u]&&!rs[u])
	{
		ans[u]=t.empty()?"0":t;
		return;
	}
	if(ls[u])dfs(ls[u],t+'0');
	if(rs[u])dfs(rs[u],t+'1');
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	priority_queue<pair<ll,int>> q;
	for(int i=1;i<=n;i++)
	{
		ll w;
		cin>>s[i]>>w;
		q.push({-w,i});
	}
	for(int i=1;i<n;i++)
	{
		auto [x,u]=q.top();
		q.pop();
		auto [y,v]=q.top();
		q.pop();
		ls[n+i]=u;
		rs[n+i]=v;
		q.push({x+y,n+i});
	}
	dfs(q.top().second);
	for(int i=1;i<=n;i++)cout<<s[i]<<' '<<ans[i]<<'\n';
	return 0;
}