哈夫曼树

浅析 数据结构：哈夫曼树

哈夫曼树是应用于编码（哈夫曼编码）的一种二叉树结构，也叫最优二叉树，哈夫曼树具有的特点为：

对于序列中的每一个数都作为叶子节点的权值，使得他们到根节点的带权路径和（叶子节点权值乘该节点到根节点路径长度）最小，那么很显然，如果一个叶子节点它的权值很大，那么它应该尽量离根节点近一些，才能保证整体最小

哈夫曼编码问题：对于一个字符序列，我们可以提前得到每个字符在序列中出现的次数（权值），现在问，如何对于序列中每一个字符，构造一个二进制数作为其编码，且满足任意一个编码不能是另一个编码的前缀（否则就编码矛盾了），且使得最终编码的整个字符序列长度最短

对于这样一个问题，我们可以将字符在序列中出现的次数作为权值，构造一颗哈夫曼树，将每个中间节点连出的两条边分别编码为0和1，最后就可以得出答案了，那么具体的构造过程如何实现呢？

哈夫曼树构造过程

这是一个贪心的过程，我们需要用一个小根堆维护序列元素，每次取出最小的两个权值，将他们连到同一个父节点上，并且设置这个父节点的权值为两个儿子权值之和，随后将这个父节点push进小根堆中，如此循环，直到最后只有一个节点（父节点），那么哈弗曼树就构造好了，此时，所有中间节点的权值和就是最终的最短编码长度

很简单，我这里现场手打一个

priority_queue<int> pq;
int ans=0;
while(pq.size()!=1){
    int temp=0;
    temp+=pq.top();pq.pop();
    temp+=pq.top();pq.pop();
    ans+=temp;
    pq.push(temp);
}
printf("%d\n",ans);

因此，就延伸出了许多这样的题目，最典型的也就是下面这题

P2168 荷马史诗（哈夫曼编码+优先队列）

这个题跟哈夫曼编码一模一样，就是把二进制数改为了k进制数，这就多出了两个需要注意的地方：

• 每次需要从堆中取出k个数，然后求和作为父节点的权值
• 有可能最后不能恰好取完所有数，也就是说，有可能存在留着根节点的儿子不用的情况，这个时候我们发现：对于一棵具有m个中间节点的哈夫曼树，它具有m*(k-1)+1个叶子节点，即m*(k-1)+1=n,从而推出(n-1)%(k-1)==0，那么如果不满足这个式子，我们可以聪明地再堆中补0，直到满足（权值为0的节点），因为我们要尽可能让权值大的节点离父亲更近，所以补0能够产生使得所有节点都往父节点方向平移的效果

除此之外，题目还要求保证总长度最短的情况下的最长字符编码的最短长度（有点绕口），那么这个只需要在维护小根堆的时候，对于权值相同的节点，我们优先选高度较低的那几个点就行了

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
// #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define All(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef double db;
typedef vector<int> VI;
typedef pair<int,int> PII;
const db PI=acos(-1.0);
const db eps=1e-6;
const ll mod=1e9+7;
const int inf=2147483647;
const int maxn=100005;
ll qpow(ll x,ll y) {ll ans=1,base=x; while(y){if(y&1)ans=(ans*base)%mod;base=(base*base)%mod;y>>=1;} return ans;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

int n,k;
ll x,ans;
struct node
{
	ll val,h;
	bool operator <(const node& rhs)const{
		if(val==rhs.val) return h>rhs.h;
		return val>rhs.val;
	}
};
priority_queue<node> pq;
int main(){
	scanf("%d%d",&n,&k);
	rep(i,1,n) scanf("%lld",&x),pq.push(node{x,1});
	while((n-1)%(k-1)!=0) pq.push(node{0,1}),n++;
	while(n>1){
		// printf("size:%d\n",pq.size());
		ll temp=0,maxh=0;
		rep(i,1,k){
			temp+=pq.top().val;
			maxh=max(maxh,pq.top().h);
			pq.pop();
		}
		ans+=temp;
		pq.push(node{temp,maxh+1});
		n-=k-1;
	}
	printf("%lld\n%lld\n",ans,pq.top().h-1);

	return 0;
}