HuffmanTree

2018-08-21

字数统计: 726字 | 阅读时长: 3min

以下摘自度娘。。。

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。
Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，
有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

构造方法：

⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n
⒉如果队列内的节点数>1，则：

⑴从队列中移除两个最大的Pi节点，即连续做两次remove(max(Pi), Priority_Queue)
⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和
⑶把（2）产生之节点加入优先队列中

⒊最后在优先队列里的点为树的根节点（root）

而此算法的时间复杂度（ Time Complexity）为O（n log n）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（log n）。

上题荷马史诗

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+100;

template<class T>
void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

int n,k,T[10*N][10],empty[10*N],tot,rt;
ll w[10*N],len[N],ans;

priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;

void build()
{
	while(!q.empty())
	{
		int tmp=q.top().second;
		q.pop();
		if(empty[tot]!=k)
		{
			T[tot][empty[tot]]=tmp;
			w[tot]+=w[tmp];
			empty[tot]++;
		}
		if(empty[tot]==k&&!q.empty())
		{
			q.push(make_pair(w[tot],tot));
			tot++;		
		}
	}
	rt=tot;
}

void dfs(int x,int dep)
{
	if(empty[x]==-1) len[x]=(ll)dep;
	for(int i=0;i<k;i++)
	{
		int to=T[x][i];
		if(to!=0)
		dfs(to,dep+1);
	}
}
int main()
{
	read(n),read(k);tot=n+1;
	for(int i=1;i<=n;i++)
	read(w[i]),q.push(make_pair(w[i],i)),empty[i]=-1;
	int tmp=n;
	while((tmp-1)%(k-1)!=0)//除了最后一层，其他层都是一个虚构节点，（k-1）个真实节点。 
	{
		q.push(make_pair(0,tot++));
		tmp++;
	}
	build();
	dfs(rt,0);
	ll mx=0;
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,len[i]),ans+=w[i]*len[i];
//		printf("%lld\n",len[i]);
	}
	printf("%lld\n%lld",ans,mx);
	return 0;
}

题解：

这基本上是一道裸的Huffman Tree的题。需注意的是若果是k进制。点数不一定满足n=1+t(k-1),t∈Z,说明n个
点不一定能构成Huffman Tree，自然也就不满足Huffman Tree的性质了，不过我们可以加入出现零次的字母，
凑出一棵树。

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/17124080.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！