知识点

一 . 哈夫曼树的定义、构造及其遍历

哈夫曼树也被称为最优二叉树，对于给定的一系列带权的叶子结点，带权路径长度WPL（Weighted Path Length）最短的二叉树。

哈夫曼树中的叶节点的个数比非叶节点的个数多一。

二 . 哈夫曼编码/霍夫曼编码 / Huffman编码

哈夫曼编码是可变字长编码（ULC）的一种。

1952年由Huffman提出的一种编码方法。完全依照字符出现的概率来构造编码，使其成为平均长度最短的编码方式，有时称为最佳编码。

哈夫曼编码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需要另外加隔开的符号，只要传送的时候不出错，接收端仍可以分离各个码字，不致混淆。

模板题

例题：

P2168 [NOI2015] 荷马史诗

思路：（待填坑）

这道题实际上要求k叉Huffman树，及由两个分叉变为k个分叉（k叉树）。

但真正去跑的时候你才发现，最后一次合并之后，堆中剩下m个值。但如果1<m<k，即没有达到

堆中只剩一个值

却

不能合并

。

所以我们使用

补点

这个方法，以达到

堆中只剩一个值

这个目的。

首先，我们每次合并用掉 k 个值又合并出1个值，那么按每次合并来算，我们每次用掉了k-1个值。然后，我们最终需要只剩1个值，即需要合并n-1个值。那么我们只需要让(n-1)%(k-1)==0 成立不就可以了，但要使(n−1)%(k-1)==0成立，我们还需要补 (k-1)−((n−1)%(k-1)) 个点，但要使答案不受影响，我们就用权值为0的点来补。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long int
using namespace std;
int n,k;
ll w,ans1=0,ans2=0;
struct tree{
	ll w,h;
};
priority_queue <tree> q;
bool operator < (tree a,tree b)
{
	if(a.w!=b.w) return a.w > b.w;
	return a.h>b.h;
}
inline ll read()
{
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

int main()
{
	n=read(); k=read();
	for(int i=1;i<=n;++i)
	{
		w=read();
		q.push((tree){w,1});
	}
	ll cnt;
	if((n-1)%(k-1)!=0) //存在节点不在哈夫曼树中
	{
		cnt=(k-1)-((n-1)%(k-1)); //需要补点的数量
		for(int i=1;i<=cnt;++i)
		{
			q.push((tree){0,1}); //把这些节点的权值标为0
		}
	}
	ll len,value;
	while(q.size()>1)
	{
		ll sumw=0,Max=0;	
		for(int i=1;i<=k;++i)
		{
		tree temp=q.top(); //在循环中取数
		len=temp.h; value=temp.w;
		sumw+=value;
		Max=max(Max,len);
		q.pop();
		}
		q.push((tree){sumw,Max+1});
		ans1+=sumw;
		ans2=max(ans2,Max); //（待填坑）为什么这里用max
	}
	printf("%lld\n%lld",ans1,ans2);	
	return 0;
}

相关练习