Java Huffuman树

分手后的思念是犯贱 2022-03-25 06:22 67阅读 0赞

问题描述

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。  
　　给出一列数\{ *p**i*\}=\{ *p*0, *p*1, …, *p**n*\-1\}，用这列数构造Huffman树的过程如下：  
　　1. 找到\{ *p**i*\}中最小的两个数，设为*p**a*和*p**b*，将*p**a*和*p**b*从\{ *p**i*\}中删除掉，然后将它们的和加入到\{ *p**i*\}中。这个过程的费用记为*p**a* \+*p**b*。  
　　2. 重复步骤1，直到\{ *p**i*\}中只剩下一个数。  
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。  
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。  
  
　　例如，对于数列\{ *p**i*\}=\{5, 3, 8, 2, 9\}，Huffman树的构造过程如下：  
　　1. 找到\{5, 3, 8, 2, 9\}中最小的两个数，分别是2和3，从\{ *p**i*\}中删除它们并将和5加入，得到\{5, 8, 9, 5\}，费用为5。  
　　2. 找到\{5, 8, 9, 5\}中最小的两个数，分别是5和5，从\{ *p**i*\}中删除它们并将和10加入，得到\{8, 9, 10\}，费用为10。  
　　3. 找到\{8, 9, 10\}中最小的两个数，分别是8和9，从\{ *p**i*\}中删除它们并将和17加入，得到\{10, 17\}，费用为17。  
　　4. 找到\{10, 17\}中最小的两个数，分别是10和17，从\{ *p**i*\}中删除它们并将和27加入，得到\{27\}，费用为27。  
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。

输入格式

输入的第一行包含一个正整数*n*（*n*<=100）。  
　　接下来是*n*个正整数，表示*p*0, *p*1, …, *p**n*\-1，每个数不超过1000。

输出格式

输出用这些数构造Huffman树的总费用。

样例输入

5  
5 3 8 2 9

样例输出

代码：

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int []arr = new int[n];
            for (int i = 0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            int count = 0;
            int tmp = arr.length-1;
            int money = 0;
            int max = 0;
            for(int i = 1;i<n;i++){
                max += arr[i];
            }
            while (arr.length != count +1){
                Arrays.sort(arr);
                money = arr[0]+arr[1] +money;
                arr[0] = arr[0]+arr[1];
    
                for(int i = 1;i<tmp;i++){
                    arr[i] = arr[i+1];
                }
                arr[arr.length-count-1] = max;
                count++;
            }
            System.out.println(money);
        }
    }