Acwing：哈夫曼树（详解）

题目描述：

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

现在，给定 N 个叶子结点的信息，请你构造哈夫曼树，并输出该树的带权路径长度。

相关知识：
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L−1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。

输入格式

第一行包含整数 N，表示叶子结点数量。

第二行包含 N 个整数，表示每个叶子结点的权值。

输出格式

输出一个整数，表示生成哈夫曼树的带权路径长度。

数据范围

2≤N≤1000
叶子结点的权值范围 [1,100]。

输入样例：

5
1 2 2 5 9

输出样例：

37

题目分析： 

本质是一道哈夫曼树概念模版题！

首先我们一定要知道什么是哈夫曼树 这里给出哈夫曼树的定义。

 这里的WPL也就是题目要求的结果

在本题中 给出了所有这颗二叉树的叶子结点 我们要做的就是用这些叶子结点构造出WPL最小的二叉树 即为哈夫曼树

显而易见的是 构造出一棵二叉树的方法是不唯一的 如下图例子

 所以 应该根据什么来构造哈夫曼树呢？观察上图发现 第一种构造方法中 权值较大的节点更加靠近根结点 这也就是哈夫曼树构造的准则 即：

 

所以总结来看 构造一颗哈夫曼树的步骤如下：

 

哈夫曼树的两个重要性质： 

1. 带权路径长度之和WPL = 所有非叶子结点的权值之和

如下图所示：

 

以 [5, 29, 7, 8, 14, 23, 3, 11] 为叶子结点构造出的哈夫曼树的WPL应该等于：

8 + 19 + 42 + 100 + 58 + 29 + 15 = 271

各位可以用WPL的计算公式验算一下。

2. 哈夫曼树的总节点数 = 2 * 叶子结点数 - 1

回归本题： 

其实看到这里 这道题的做法已经很清晰了

首先将所有叶子结点放在一个堆中

我们只需要每次取出最小的两个节点 将他们的权值相加后放回堆中 同时累加答案（相加之后的权值之和）直到堆内只剩下最后一个点 即为根结点。

AC代码： 

import heapq

N = int(input())
lst = list(map(int,input().split()))
heapq.heapify(lst)
res = 0

while len(lst) > 1 :
    a = heapq.heappop(lst)
    b = heapq.heappop(lst)
    heapq.heappush(lst,a+b)
    res += a+b
    
print(res)

相关资源：哈夫曼树和哈夫曼编码_哔哩哔哩_bilibili