本文主要是介绍蓝桥杯vip试题 基础练习 Huffuman树（java实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
2. 重复步骤1，直到{pi}中只剩下一个数。
在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。
例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入格式
输入的第一行包含一个正整数n（n<=100）。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出格式
输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59
我的分析：这题的关键字虽然是贪心和Huffman，但是不用你真正去写个构造哈夫曼树的代码出来。仔细阅读题目，它就是想让你实现生成哈夫曼树中取最小两个的和再加入“原集合”这个关键步骤。而要实现这个，我们可以借助优先队列来存储元素。因为每次都取最小的两个，而且每次都要插入新元素重新排序，这都符合优先队列的特性。最棒的是，java已经给我们提供了优先队列类PriorityQueue<E>，里面有很多实用且必要的方法，如：int size()返回此优先队列中的元素数；boolean offer(E e)将指定的元素插入此优先队列；E poll()获取并移除此队列的头，如果此队列为空，则返回null。public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)这个构造方法可以让我们自定义该队列的优先规则，也就是如何排序，在本题中，我们当然是要求最小的，即最小的在队头，所以是从小到大排序。如果有小伙伴还不知道什么是优先队列，你们可以参考这篇微信文章https://mp.weixin.qq.com/s/wFE8Pv1Mw0Ukd1o4EXtWEw，我是看了很多资料看到这篇文章才理解清楚优先队列。
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int weights = 0;Integer min1, min2, newNode;PriorityQueue<Integer> pq = new PriorityQueue<Integer>(n, new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {return o1 - o2;}});for (int i = 0; i < n; i++) pq.offer(in.nextInt());while (pq.size() > 1) {min1 = pq.poll();min2 = pq.poll();newNode = min1 + min2;weights += newNode;pq.offer(newNode);}System.out.println(weights);in.close();}}这篇关于蓝桥杯vip试题 基础练习 Huffuman树（java实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
