题目链接：https://www.acwing.com/problem/content/description/151/
给定长度为n的序列，代表一个单词的出现次数，要求构造k叉哈夫曼树使得总权值最小，并且在权值最小的情况下问最小的高度是多少？
我们可以考虑不断取k个数组成一个新的结点放入优先队列，但是根节点可能不满k叉，所以可以考虑在其中不超过k-1个零来上调权值比较大的结点，权值为零的结点肯定在最深层的一个父节点上。
也只有这一个父节点是不满k叉的，这个可以通过贪心的思想进行验证，接下来考虑深度最小，我们在合并的时候，值不同的节点在同一轮取数中取出来之后无法更优，只能按照顺序拼接，但是
如果结点的值一样的时候我们需要优先选择高度比较小的来合并，因为我们的哈夫曼树是从下到上构建的，高度大的数可以放到下一轮合并中，可以证明这样的选择更优，故在优先级队列中我们
需要维护两个关键字，一个是当前树的权重和，一个是高度，使用pair<long long ,int>存储。
其次，每一轮取数中height的更新方式是，新构造的结点的height是子节点的height的最大值+1，注意取出来的结点一定是已经满足上面两种关键字最优性的。
代码：
#include<iostream> #include<cstdio> #include<queue> typedef long long ll; #define PLI pair<ll,int> using namespace std; int main(){ int n,k; cin>>n>>k; priority_queue<PLI,vector<PLI>,greater<PLI> > pq; for(int i=0;i<n;i++){ ll x; cin>>x; pq.push({x,0}); } while((n-1)%(k-1))n++,pq.push({0,0});//保证k叉树每个结点都有k个叉，并且最深处的结点存在为0的点 ll res=0; while(pq.size()>1){ ll s=0; int height=0; for(int i=0;i<k;i++){//构造一个结点 PLI p=pq.top(); s+=p.first; height=max(height,p.second);//计算结点的高度，等于子节点的最大高度加一 pq.pop(); } res+=s; pq.push({s,height+1}); } cout<<res<<endl<<pq.top().second<<endl; }
《算法竞赛进阶指南》0x17二叉堆 利用优先队列求k叉哈夫曼树的最优结构
原文：https://www.cnblogs.com/randy-lo/p/13158129.html