哈夫曼树，哈夫曼编码：
一、哈夫曼树：
①、哈夫曼编码是一种高效的编码方法，在信息论中具有重要地位。
P1090 合并果子问题：
题目描述：
在一个果园中，多多已经将所有种类的果子分成了不同的堆。多多决定将所有水果合并成一堆以便于运输和管理。
每一次合并不只是简单地将两团成果放置在一起, 而是需要多多付出相应的努力, 这种努力具体表现为两团成果重量相加所带来的体能消耗. 很明显, 在经历了n−1次这样的合并不断推进之后, 最终只会剩下最后一团成果. 而在整个过程中, 多多一共耗费的能量就是每次合并不断积累下来的总能量.
由于也需耗费大量体力将这些果子运回家中，在合并果子的过程中多多应尽量最大限度地减少体力消耗
举例来说有三种类型的果子其数量分别为1、2和9个。我们可以先将数量较少的两种进行合并具体来说就是将数量为1和2的果子堆进行结合这样会消耗掉3个单位的体⼒形成一个新的果子堆其数量变为3个。随后我们将这个新形成的果子堆与原有的数量为9个的第三种果子堆进行合并这样又会形成一个新的更大的果子堆其数量达到12个并消耗掉额外的体⼒即12个单位。经过以上两步操作多多总共所消耗的体⼒计算结果是3+12=15单位这表明通过上述策略所获得的总体⼒消耗是最小值
输入格式
共两行。
第一行是一个整数 n ，表示果子的种类数。
第二行包含 n 个整数，用空格分隔，第 i 个整数 是第 i 种果子的数目。
输出格式
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2^31
输入输出样例
输入 #1 复制
3
1 2 9
输出 #1 复制
15
说明/提示
对于30％的数据，保证有n≤1000：
对于50％的数据，保证有n≤5000；
对于全部的数据，保证有n≤10000。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
int main(void)
{
int n,x,ans=0;
priority_queue<int>q;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
q.push(-x);
}
while(q.size()>1)
{
int now=0;
now+=q.top();
q.pop();
now+=q.top();
q.pop();
ans-=now;
q.push(now);
}
printf("%d\n",ans);
return 0;
}②、Sort HDU - 5884 ：
最近一段时间里, Bob刚刚掌握了基础的归并排序算法:归并排序法的基本思想就是将数组不断分割然后逐步合并最终得到一个有序数组。现在, Bob收到了一项来自Alice的任务：
Alice会给出Bob N个已排序序列,其中第i个序列包含ai个元素。Bob的任务是将这些序列进行合并操作。他可以编写一个程序,但每次运行时最多只能同时处理不超过k个序列的合并操作;每一次合并操作的成本等于参与合并的所有序列长度之和。不幸的是,Alice规定该程序执行过程中的总成本不能超过T这个限制值;因此,Bob希望找到最小的k值使得整个程序能够在规定时间内完成任务
输入
第一行输入包含一个整数t0,表示测试用例的数量；接下来t0个测试用例依次给出具体数据
每个测试用例的第一行包含两个整数N(2≤N≤105)以及T(∑Ni=1ai<T<231)
在接下来的一行中给出N个整数a1,a2,a3,…aN(∀i, 0≤ai≤10^3)
输出
对于每一个测试用例来说,输出满足条件的最小k值
样例输入：
1
5 25
1 2 3 4 5
样例输出：
3
一次哈夫曼树的时间复杂度为n \log n，再加上二分法的一个\log n操作后，则大致是(n \log n) \times (\log n)。然而，在本题中可以通过序列的单调性特性，在不改变原有算法的基础上巧妙地引入两个队列来进行数据管理。这样一来，在构建哈夫曼树的过程中每一步的时间复杂度将被降低到O(n)量级。总体而言，在完成上述步骤之后的过程所呈现出来的总时间复杂度为n \log n
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
ll a[maxn],n,res;
bool check(int k)
{
queue<ll>q1,q2;
ll ans=0,temp=0;
int tm=(n-1)%(k-1);
if(tm)
for(int i=1;i<=k-1-tm;i++)
q1.push(0);
for(int i=1;i<=n;i++)
q1.push(a[i]);
while(q1.size()+q2.size()>=2)
{
temp=0;
for(int i=1;i<=k;i++)
{
if(q1.size()&&q2.size())
{
if(q1.front()<q2.front())
temp+=q1.front(),q1.pop();
else temp+=q2.front(),q2.pop();
}
else if(q1.size())
temp+=q1.front(),q1.pop();
else if(q2.size())
temp+=q2.front(),q2.pop();
}
ans+=temp;
q2.push(temp);
}
return ans<=res;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&n,&res);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
int pos=2,l=2,r=n;
int mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) pos=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",pos);
}
}二、哈夫曼编码：
P2168 [NOI2015]荷马史诗：
追逐影子的人，自己就是影子 ——荷马
Allison 最近迷恋上了文学领域，在慵懒的午后慢慢品味一杯咖啡香浓的卡布奇诺时会陷入沉醉式的专注状态，在这样的时刻她的爱书《荷马史诗》往往能让她无法自拔地投入其中。然而这部由 Homer 的 《奥德赛》与 《伊利亚特》 所构成的经典著作 《荷马史诗》 是一部令人惊叹的宏篇巨著其浩瀚内容令 Allison 想象不到想要找到一种高效编码手段来缩减其冗长程度
在《荷马史诗》这部作品中存在n个独特的词汇，在这些词汇中按照从1到n的顺序进行标记。其中每个第i个词汇在文本中共出现了wi次。Allison打算将每个第i个词汇替换为其对应的k进制编码si，并且这种编码必须满足特定的要求。
对于任意的 1 ≤ i, j ≤ n ， i ≠ j ，都有：si不是sj的前缀。
Allison想要确定si的选择，在确保新《荷马史诗》达到最短总长度的前提下，她还想确定最长的那个si的具体最小值。
一个字符串被视为k进制字符串，满足以下条件：即其所有字符都属于从0开始一直到k−1之间的整数范围。
字符串 str₁ 被称作字符串 str₂ 的前缀，在特定情况下成立：当且仅当存在一个整数 t 满足 1 ≤ t ≤ m 时，则有 str₁ 等于 str₂ 的前 t 个字符组成的子串。其中 m 是 str₂ 的长度；而该子串即为从第一个字符到第 t 个字符连接而成的序列。
在输入的第一行中存在两个正整数n和k之间以一个空格分隔，在表示共有n种不同的单词时需要用k进制字符串来进行替换操作
接下来n行，第 i + 1 行包含 1 个非负整数wi ，表示第 i 种单词的出现次数。
输出格式
输出包括 2 行。
第 1 行输出 1 个整数，为《荷马史诗》经过重新编码以后的最短长度。
第 2 行输出 1 个整数，为保证最短总长度的情况下，最长字符串 si 的最短长度。
输入输出样例
输入 #1 复制
4 2
1
1
2
2
输出 #1 复制
12
2
输入 #2 复制
6 3
1
1
3
3
9
9
输出 #2 复制
36
3
说明/提示
【样例说明 1】
用 X(k) 表示 X 是以 k 进制表示的字符串。
最佳方案设定：采用二进制码组00^{(2)}对应替换第一类词汇,01^{(2)}对应替换第二类词汇,10^{(2)}对应替换第三类词汇,11^{(2)}对应替换第四类词汇。按照上述方案实施后,编码后的信息序列最小码长为:
1 × 2 + 1 × 2 + 2 × 2 + 2 × 2 = 12
最长字符串si的长度为 2 。
一种非最优方案：采用代码 000_{(2)} 对应第一种单词、001_{(2)} 对应第二种单词、01_{(2)} 对应第三种单词以及 1_{(2)} 对应第四种单词。在此方案下其编码后的最短长度为
1 × 3 + 1 × 3 + 2 × 2 + 2 × 1 = 12
最大连续子串 si 的其长度为 3 。相较于最优方案而言，在总长度上二者一致，并未见有较长的最大连续子串出现。
【样例说明 2】
最佳方案设定 规则如下：将编号为"³"的单元格赋值给第一种单词 将编号为"³"的单元格赋值给第二种单词 将编号为"³"的单元格赋值给第三种单词 将编号为"³"的单元格赋值给第四种单词 将编号为"³"的单元格赋值给第五种单词 最后将编号为"³"的单元格赋值给第六种单词
n<=1e5
k<=9
wi<=1e11
本题规定，在满足条件的情况下, 最长编码应尽可能地简短. 当处理相同权值的节点时, 请优先选择当前深度最低且已合并次数最少的情况进行结合.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
struct node
{
ll wi;
ll d;
node(){}
node(const ll &a,const ll &b)
{
wi=a,d=b;
}
friend bool operator<(const node&a,const node &b)
{
if(a.wi!=b.wi) return a.wi>b.wi;
else return a.d>b.d;
}
};
int main(void)
{
int n,k;
ll ans=0,maxx=0,res=0,x;
scanf("%d%d",&n,&k);
priority_queue<node>q;
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
q.push(node(x,0));
}
int tm=(n-1)%(k-1);
if(tm)
for(int i=1;i<=k-1-tm;i++)
q.push(node(0,0));
while(q.size()>=2)
{
maxx=res=0;
for(int i=1;i<=k;i++)
{
res+=q.top().wi;
maxx=max(maxx,q.top().d);
q.pop();
}
ans+=res;
q.push(node(res,maxx+1));
}
printf("%lld\n%lld\n",ans,q.top().d);
return 0;
}