Skip to main content

霍夫曼树

Summary

霍夫曼树是带权路径长度 WPL 最小的二叉树，WPL 定义为所有叶结点的权值与其到根路径长度之积的总和。霍夫曼算法的核心是贪心：每次从集合中取出权值最小的两棵树合并为新树，新根权为两子树权值之和，再放回集合，重复 n 减 1 次直到只剩一棵；权值越小的叶结点离根越远、越大的越近，从而最小化 WPL。构建用小根堆实现，复杂度 O(nlogn)，WPL 恰等于每次合并时两树权值之和的累计。给出用优先队列不断取两小相加求 WPL 的实现。

参考资料​

简介​

霍夫曼树（Huffman Tree）是带权路径长度（Weighted Path Length，WPL）最小的二叉树，其中 WPL 定义为所有叶结点的权值乘以其到根路径长度之积的总和：

WPL=∑i=1nwili\mathrm{WPL}=\sum_{i=1}^n w_i l_i

霍夫曼算法的核心思想：每次从集合中选出权值最小的两棵树合并为新树，新树根权值为两子树权值之和，再放回集合，重复 n−1n-1 次直至只剩一棵树。权值越小的叶结点离根越远，权值越大的离根越近，从而使 WPL 最小。

构建过程可用小根堆实现，时间复杂度为 O(nlog⁡n)O(n\log n)。WPL 等于每次合并时两棵树权值之和的累计总和。

实现​

429 Bcpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	priority_queue<long long,vector<long long>,greater<long long>> pq;
	for(int i=0;i<n;i++)
	{
		long long x;
		cin>>x;
		pq.push(x);
	}
	long long ans=0;
	while(pq.size()>1)
	{
		long long x=pq.top();pq.pop();
		long long y=pq.top();pq.pop();
		ans+=x+y;
		pq.push(x+y);
	}
	cout<<ans<<'\n';
	return 0;
}

例题​

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

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

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

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