k叉 huffman 树的$O(n)$ 算法
思想为开两个队列,第一个为权值排序后的队列
第二个存储的是每次合并后的值
每次从两个队列首部选k个最小的数,然后合并
作为一个新的节点加入第二个队列尾部

p.s. 注意若$(n-1) \pmod{k-1} \neq 0$,则要先将最小的$(n-1)\pmod{k-1}+1$个数先合并一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

queue<int> q;
int a[maxn];

int huffman(int n,int k)
{
sort(a,a+n);
int j = 0,cur = 0,cost = 0;
if((n-1) % (k-1))
{
for(int i=0;i<(n-1)%(k-1)+1;++i)
cur += a[j++];
q.push(cur);
cost += cur;
}
while(q.size() > 1 || j < n)
{
cur = 0;
for(int i=0;i<k;++i)
{
if(j < n && (!q.size() || q.front() > a[j])) cur += a[j],++j;
if(q.size() && (j >= n || q.front() <= a[j])) cur += q.front(),q.pop();
if(!q.size() && j >= n) break;
}
q.push(cur);
}
return cost;
}