请选择 进入手机版 | 继续访问电脑版
在线投稿 文字标题 文字标题 文字标题 文字标题 文字标题
切换皮肤
[size=0.26]

?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F56a94f33j00q8juv40009d200dw00dwg00dw00dw.jpg

作者 | 小灰
来源 | 程序员小灰(ID:chengxuyuanxiaohui)
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F00ee5629j00q8juv4000hd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F769bef51j00q8juv4000hd200i200b4g00i200b4.jpg
————— 第二天 —————
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F9b485ab9j00q8juv4000hd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F1eebd17cj00q8juv5000gd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F89ee7a82j00q8juv6000kd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F00036ac4j00q8juv6000jd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fc377bda0j00q8juv6000id200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fdf7eb83ej00q8juv7000ed200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F54d36db2j00q8juv7000fd200i200b4g00i200b4.jpg
————————————
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F787d1ce3j00q8juv7000id200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F1e56bbb1j00q8juv7000ed200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F4d5ec346j00q8juv7000kd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fbba0f326j00q8juv8000md200i200b4g00i200b4.jpg
概念1:什么是路径?
在一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径。
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F9ea8cdb7p00q8juv8000td200fp00djg00c500ag.jpg
上面的二叉树当中,从根结点A到叶子结点H的路径,就是A,B,D,H。
概念2:什么是路径长度?
在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度。
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fbe69c6bcp00q8juv9000vd200fp00djg00cg00aq.jpg
仍然用刚才的二叉树举例子,从根结点A到叶子结点H,共经过了3条边,因此路径长度是3。
概念3:什么是结点的带权路径长度?
树的每一个结点,都可以拥有自己的“权重”(Weight),权重在不同的算法当中可以起到不同的作用。
结点的带权路径长度,是指树的根结点到该结点的路径长度,和该结点权重的乘积。
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F03e8a81bp00q8juv9000wd200fp00f8g00d000cl.jpg
假设结点H的权重是3,从根结点到结点H的路径长度也是3,因此结点H的带权路径长度是 3 X 3 = 9。
概念4:什么是树的带权路径长度?
在一棵树中,所有叶子结点的带权路径长度之和,被称为树的带权路径长度,也被简称为WPL。
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F9fe397bcp00q8juv9000sd200fp00f8g00cr00cd.jpg
仍然以这颗二叉树为例,树的路径长度是 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53。
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fb66a2224j00q8juva000kd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F154c51a3j00q8juva000sd200i200b4g00i200b4.jpg
哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明,这到底是一颗什么样的树呢?
刚才我们学习了树的带权路径长度(WPL),而哈夫曼树(Huffman Tree)是在叶子结点和权重确定的情况下,带权路径长度最小的二叉树,也被称为最优二叉树。
举个例子,给定权重分别为1,3,4,6,8的叶子结点,我们应当构建怎样的二叉树,才能保证其带权路径长度最小?
原则上,我们应该让权重小的叶子结点远离树根,权重大的叶子结点靠近树根。
下图左侧的这棵树就是一颗哈夫曼树,它的WPL是46,小于之前例子当中的53:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Ff31f2622p00q8juvb001xd200t500dlg00id008k.jpg
需要注意的是,同样叶子结点所构成的哈夫曼树可能不止一颗,下面这几棵树都是哈夫曼树:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F96d2565ap00q8juvb001wd200u00086g00id004z.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fc0273a8dj00q8juvb000rd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F5aab46e0j00q8juvb000od200i200b4g00i200b4.jpg
假设有6个叶子结点,权重依次是2,3,7,9,18,25,如何构建一颗哈夫曼树,也就是带权路径长度最小的树呢?
第一步:构建森林
我们把每一个叶子结点,都当做树一颗独立的树(只有根结点的树),这样就形成了一个森林:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F4ddc1d8cp00q8juvc000ad200ir00ffg00e400bl.jpg
在上图当中,右侧是叶子结点的森林,左侧是一个辅助队列,按照权值从小到大存储了所有叶子结点。至于辅助队列的作用,我们后续将会看到。
第二步:选择当前权值最小的两个结点,生成新的父结点
借助辅助队列,我们可以找到权值最小的结点2和3,并根据这两个结点生成一个新的父结点,父节点的权值是这两个结点权值之和:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F2bc34388p00q8juvd000qd200ir00ffg00id00f3.jpg
第三步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列
也就是从队列中删除2和3,插入5,并且仍然保持队列的升序:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F65d0671fp00q8juvd000pd200ir00dtg00id00di.jpg
第四步:选择当前权值最小的两个结点,生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是5和7,生成新的父结点权值是5+7=12:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F5637b925p00q8juvd000sd200ir00dtg00id00di.jpg
第五步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列。
这是对第三步的重复操作,也就是从队列中删除5和7,插入12,并且仍然保持队列的升序:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fa83efbe4p00q8juve000rd200ii00b8g00id00b4.jpg
第六步:选择当前权值最小的两个结点,生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是9和12,生成新的父结点权值是9+12=21:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F4eea6a88p00q8juve000wd200j400c1g00id00bk.jpg
第七步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列。
这是对第三步的重复操作,也就是从队列中删除9和12,插入21,并且仍然保持队列的升序:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F630bcc47p00q8juve000wd200ky00c1g00id00aj.jpg
第八步:选择当前权值最小的两个结点,生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是18和21,生成新的父结点权值是18+21=39:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F4859e2a1p00q8juve0013d200l500f6g00id00d6.jpg
第九步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列。
这是对第三步的重复操作,也就是从队列中删除18和21,插入39,并且仍然保持队列的升序:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F4e739479p00q8juvf0013d200l500f6g00id00d6.jpg
第十步:选择当前权值最小的两个结点,生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是25和39,生成新的父结点权值是25+39=64:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F4cb469efp00q8juvf0019d200jr00hzg00id00gp.jpg
第十一步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列
这是对第三步的重复操作,也就是从队列中删除25和39,插入64:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F30b08ab3p00q8juvg0018d200jr00hzg00id00gp.jpg
此时,队列中仅有一个结点,说明整个森林已经合并成了一颗树,而这棵树就是我们想要的哈夫曼树:
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Fc910860cp00q8juvg000zd200bh00hzg008g00d8.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F450aa31fj00q8juvg000od200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F66af542cj00q8juvh000jd200i200b4g00i200b4.jpg
private Node root;
private Node[] nodes;
//构建哈夫曼树
public void createHuffman(int[] weights) {
//优先队列,用于辅助构建哈夫曼树
Queue nodeQueue = new PriorityQueue<>();
nodes = new Node[weights.length];

//构建森林,初始化nodes数组
for( int i= 0; i nodes = new Node(weights);
nodeQueue.add(nodes);
}

//主循环,当结点队列只剩一个结点时结束
while (nodeQueue.size() > 1) {
//从结点队列选择权值最小的两个结点
Node left = nodeQueue.poll();
Node right = nodeQueue.poll();
//创建新结点作为两结点的父节点
Node parent = new Node(left.weight + right.weight, left, right);
nodeQueue.add(parent);
}
root = nodeQueue.poll();
}
//按照前序遍历输出
public void output(Node head) {
if(head == null){
return;
}
System.out.println(head.weight);
output(head.lChild);
output(head.rChild);
}
public static class Node implements Comparable{
int weight;
Node lChild;
Node rChild;

public Node(int weight) {
this.weight = weight;
}

public Node(int weight, Node lChild, Node rChild) {
this.weight = weight;
this.lChild = lChild;
this.rChild = rChild;
}

@Override
public int compareTo(Node o) {
return new Integer( this.weight).compareTo( new Integer(o.weight));
}
}
public static void main(String[] args) {
int[] weights = { 2, 3, 7, 9, 18, 25};
HuffmanTree huffmanTree = new HuffmanTree();
huffmanTree.createHuffman(weights);
huffmanTree.output(huffmanTree.root);
}
在这段代码中,为了保证结点队列当中的结点始终按照权值升序排列,我们使用了优先队列PriorityQueue。
与此同时,静态内部类Node需要实现比较接口,重写compareTo方法,以保证Node对象在进入队列时按照权值来比较。
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F5a9e729dj00q8juvh000kd200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F2bfc89f8j00q8juvh000td200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F8755dce3j00q8juvi000md200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F16018d38j00q8juvi000id200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2Ff542db0fj00q8juvi000md200i200b4g00i200b4.jpg
?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0410%2F92341806j00q8juvi000rd200i200b4g00i200b4.jpg
【END】

回复

使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则


    Archiver|手机版|小黑屋|齐聚无忧 |网站地图

    Powered by Discuz! X3.4  © 2001-2013 Comsenz Inc.