牛客北邮复试真题 哈夫曼树_北邮考研 哈夫曼

题目描述
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

示例

输入
5
1 2 2 5 9
输出
37

思路
重要的是怎么算权值，采用叠加的办法，例如本示例中，1和2是最深的两个数，我首先进入了一个误区就是一定要算出每个结点在哈夫曼树中的高度，在这样的考虑下对于记录高度和对应节点都有一定困难，这里要提出一种代码的思想，计算机中的乘法是由加法累加而成的，当遇到不知道如何取乘数的情况可以考虑用加法来代替
在本题中，每个非叶子节点都是有权值的，而这个权值即为下面的叶子节点的和，那么将一条路径上的所有叶子节点和非叶子节点的权值全部相加就能得到乘法的效果

解题关键是权值的求法：
赫夫曼树的带权路径之和为各叶子节点的权值与路径长度（层次数减一或从根节点到达叶子节点路径上的非叶子节点的个数）之积的和。在构造赫夫曼树时，非叶子节点也会带有权值（为其子节点的权值之和），当加上一个非叶子节点的权值时相当于加上以其为根节点的子树的所有叶子节点的权值。而加上从根节点到叶子节点路径上的非叶子节点权值，就包含了该叶子节点的带权路径长度。所以带权路径之和即为所有非叶子节点的权值之和。
接下来就是按照构造赫夫曼树的方法求出各非叶子节点的权值。
关键在于选取节点中最小的两个节点，并删除这两节点并添加新的节点。

有这种思路之后本题即化简为排序输出相加的问题

优先队列
Java中有一种数据结构为：优先队列

优先队列PriorityQueue是Queue接口的实现，可以对其中元素进行排序，可以放基本数据类型的包装类（如：Integer，Long等）或自定义的类，对于基本数据类型的包装器类，优先队列中元素默认排列顺序是升序排列

其常用方法为：

peek()//返回队首元素
poll()//返回队首元素，队首元素出队列
add()//添加元素
size()//返回队列元素个数
isEmpty()//判断队列是否为空，为空返回true,不空返回false

本题采用优先队列十分简单，代码如下：

package niuKe;
import java.util.Scanner;
import java.util.PriorityQueue;

public class Haffuma {
/*	
 *   找到数组中最小的两个数
 */
	public static void main(String[]args) {
		Scanner input = new Scanner(System.in);   // import的快捷键是Ctrl + shift + o
		while(input.hasNext()) {
			int n = input.nextInt();
			PriorityQueue<Integer> que = new PriorityQueue<Integer>();  //优先级数组
			while(n > 0) {
				que.add(input.nextInt());
				n--;
			}
			int ans = 0;
			int fir = 0;
			int sec = 0;
			while(que.size() > 1) {
				fir = que.poll();
				sec = que.poll();
				ans += (fir + sec);
				que.add(fir + sec);
			}
			System.out.println(ans);
		}
		
	}
}

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
29
30
31
32