上一篇文章《重编码-Huffman树WPL问题》解释了二叉Huffman树WPL问题,而这道题将二叉拓展到了K叉。
K叉与二叉的区别主要在一下几个地方
- 节点数可能不足以满足K叉Huffman树的结构,需要补充虚拟节点。
- 在弹出节点时不是弹出2个,而是K个。
再就是本体还需要输出最长字符串的最短长度,也就是Huffman编码的最长长度。这里我们用一个pair来维护该节点在Huffman树的深度,也就是所求值。
先给出参考代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long,long long>;
int n,k;
priority_queue<pll,vector<pll>,greater<pll> > q;
ll ans;
int main() {
ios::sync_with_stdio(false);
cin >> n >> k;
ll temp;
for(int i = 1; i <= n; ++i) {
cin >> temp;
q.push({temp,0});
}
while((q.size() - 1) % (k - 1))
q.push({0,0});
while(q.size() >= (unsigned long int) k) {
ll depth = -1;
ll sum = 0;
for(int i = 1; i <= k ; ++i) {
sum += q.top().first;
depth = max(depth,q.top().second);
q.pop();
}
q.push({sum,depth + 1});
ans += sum;
}
cout << ans << endl << q.top().second << endl;
return 0;
}
这里解释几个个关键性的问题:
为什么要使节点数满足(q.size() - 1) % (k - 1) = 0?
为了防止在最后有节点剩余而无法合并,此时的局面不为最优解(此时答案偏小)。这个时候添加词频为0的虚拟节点可以满足K叉Huffman树的结构且不会影响到答案(相当于把节点“挤”到更优位置)。
如何证明这个算法是对的?
其实和二叉Huffman树的道理是一样的,只不过我们在这里拓展成了K叉而已,如果还是无法理解算法过程可以手动模拟一遍。
(我懒,就不放模拟过程的图了)
节点的深度是如何维护的?
道理很简单,对于一个节点,我们弹出来求了一次和(sum),就相当于把这层深度上的K叉Huffman树节点“砍掉了”。这个时候我们只需要找出这之中最大深度加上1,就可以维护节点最大深度了。