【OI之路】09经典问题-3哈夫曼树

哈夫曼树

定义

定义树的带权路径长度(wpl)是
每个叶子节点,其【权值×节点到根的带权距离】之和

定义“满足国际定义的满k叉树”是
每个节点,其孩子个数不是0就是k

相关介绍:
百度百科-满二叉树(借鉴一下)
这里稍微有提到,省略了“国际”:
百度百科-哈夫曼树

因为没有时间,不详细介绍
有兴趣的童鞋可以去wiki看看专业文献

哈夫曼树(霍夫曼树)

1.
给出n个叶子节点,求一个k叉树结构,使得这棵树的带权路径长度和最小

2.
先考虑k=2的二叉树情况
由定义,可以想到一个贪心:
每次取出最小的a和b,累计答案a+b,并构造父亲节点,权值为a+b
(其实很多算法都是从贪心开始的,虽然不一定以此结束)
必要性证明:不会
充分性证明:把(a+b)×深度,拆分成父亲(深度-1)和答案里面的a+b

然后,由于带权路径长度的特殊性
如果我们已经限定了k=2,生成的树一定是满足国际定义的满k叉树
必要性证明:假设某个非底层位置还剩个“槽”,
把某个比这里深的节点(这意味着它比这几个叶子节点小)移到这里,
一定能让答案更小

例题:
noip2004 合并果子
把参与合并次数作为深度就好了

3.
当k>2呢?我们能不能改成一次拿出k个?
有一个要考虑的细节:再刚才,k=2,总能取到这么多
然鹅现在,有可能最后剩下<k个
由于上面的证明,我们需要生成满足国际定义的满k叉树,才能确保正确性
其实解决办法很简单:
补0,直到能生成满足国际定义的满k叉树
这样就把本来应该放在顶层(其实就是非顶层里面最大的那些)放到顶层

但是怎么判断能不能生成完全k叉树呢?
换句话说,生成满足国际定义的满k叉树对叶子节点数量有什么要求?
结论:(n-1)%(k-1)=0
充分性证明:
假设有n个叶子节点,它们能生成满足国际定义的满k叉树
先看根节点,隐去剩下的n-1个节点,倒过来考虑
每一次,我们给它k个孩子节点,但同时它自己不再是叶子节点
所以每一次,那n-1个节点,按照一次k-1个来出现
所以n-1应当是k-1的倍数

哈夫曼Huffman编码

哈夫曼有个特性,就是能够解决编码问题
把每个字母、单词的出现次数统计起来,给其新的编码,
总长度总是最小的(可以把次数看作权值,长度看作深度)
而且,这个编码的优秀在于不会有歧义
换句话说,一个编码不会是另外一个编码的前缀

做法:
生成哈夫曼树,如果编码是k进制的,也就是0~k-1的
那么可以理解为是k叉的,然后按照0~k-1给同一个父亲到它孩子的边赋权
然后上面说的前缀,原因在于我们把字母、单词看作叶子节点
从根节点到达它,经过的权,其排列是独一无二的
(后缀就不一定了,但没有关系,因为解码的时候是从前往后的,先入为主)

例题:
noi2015 荷马史诗

其他经典

Tag-哈夫曼

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/f6c6.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%