秋招每日一题T19——哈夫曼树

题目描述

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

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

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

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

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

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

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

思路

①特别喜欢AcWing题解里对于本题理解的一段话：数据结构的外表，贪心的内在。想要使树的带权路径长度达到最小，那么权小的结点应该尽可能优先进入哈夫曼树。
②两个结点分别构成新生成结点的左右孩子，而这个新生成的结点的权就是左右孩子的带权最短路径（如果左右孩子也有叶子节点，那么它们的权会被重复累加，巧妙地满足了权×距离树根长度的计算方法）
③因此这个题成功地转化为了贪心问题，即通过优先队列priority_queue，找到权值最小的两个结点，生成新的结点后再次加入小根堆。
④最后仅剩的一个结点是哈夫曼树的根节点，代表着整棵树的带全最短路径长度。
⑤本题来自北京邮电大学考研机试。

代码

#include 
#include 
#include 
#include 
using namespace std;
priority_queue<int,vector<int>,greater<int> > halfman;
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		halfman.push(x);
	}
	int res = 0;
	while(halfman.size() > 1){
		int x1 = halfman.top();
		halfman.pop();
		int x2 = halfman.top();
		halfman.pop();
		int x3 = x1 + x2;
		res += x3;
		halfman.push(x3);
	}
	cout<<res;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28