解析
解析
给定N个权值作为N个叶子节点,构造一棵二叉树,若该树的带权路径长度****(WPL)达到最小,称这样的二叉树为最优二叉树,也称为**哈夫曼树(Huffman Tree)**。
哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
参考:霍夫曼树(参考该文章中的概念,其中代码不对)
树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)
如下图中的哈夫曼树,其WPL的值 = (2+3) * 3 + 4 * 2 + 6 * 1 = 29
下面的2个网站中的实现都差不多,都借助了优先队列来进行排序(java是PriorityQueue,python是heapq)
1 | class SortedList{ |
1 | class FirstLastList_long{ |
1 | class Link_long{ //链节点类 |
1.下载python3.8
1 | cd ~/Download |
解压
1 | tar -zxvf Python-3.8.11.tgz |
2.创建目录
1 | cd /usr/local |
3.编译安装
1 | ./configure prefix=/usr/local/python/python3.8 --enable-optimizations |
4.配置环境变量
1 | # python |
参考:Ubuntu16.04安装Python3.8,3.7,3.9(含卸载方法,支持多版本共存)
1 | import java.util.Arrays; |
1 | class PriorityQueue{ |