ブルーブリッジカップ-Huffmanツリー(VIP試験問題)

問題の説明
Huffmanツリーは符号化に広く応用されている.ここでは,Huffman樹の構造過程のみに関心を持つ.列数{pi}={p 0,p 1,...,pn−1}を与え,この列数でHuffmanツリーを構築する過程は以下の通りである.{pi}の最小の2つの数を見つけ、paとpbに設定し、paとpbを{pi}から削除し、それらの和を{pi}に追加します.このプロセスの費用はpa+pbと記す.　　2.手順1を繰り返し、{pi}に数が1つしか残っていないまで繰り返します.上の操作過程ですべての費用を加算すると,Huffmanツリーを構築する総費用が得られる.このタスク:指定された数列について、Huffmanツリーをこの数列で構築する総費用を求めます.例えば,数列{pi}={5,3,8,2,9}について,Huffmanツリーの構造過程は以下の通りである.{5,3,8,2,9}の最小の2つの数を見つけ,それぞれ2と3であり,{pi}からそれらを削除し,和5を加え,{5,8,9,5}を得,費用は5であった.　　2.{5,8,9,5}の最小の2つの数を見つけて、それぞれ5と5で、{pi}からそれらを削除して10と追加して、{8,9,10}を得て、費用は10です.　　3.{8,9,10}の最小の2つの数を見つけて、それぞれ8と9で、{pi}からそれらを削除して17を加えて、{10,17}を得て、費用は17です.　　4.{10,17}の最小の2つの数を見つけて、それぞれ10と17で、{pi}からそれらを削除して27を加えて、{27}を得て、費用は27です.　　5.現在、数列には1つの数27しか残っておらず、構造過程は終了し、総費用は5+10+17+27=59となっている.
入力フォーマット
入力された最初の行には、正の整数n(n<=100)が含まれます.次に、p 0、p 1、...、pn-1を表し、各数は1000を超えません.
出力フォーマット
これらの数でHuffmanツリーを構築する総費用を出力します.
サンプル入力
5 5 3 8 2 9
サンプル出力
59

import java.util.Arrays;
import java.util.Scanner;

public class Huffman {
	public static void main(String[] args)throws Exception{
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int num = scanner.nextInt();
			int[] huff = new int[num];
			for (int i = 0; i < num; i++)
				huff[i] = scanner.nextInt();
			int sum = 0;
			int k = 0;
			while (num > 1) {
				Arrays.sort(huff);
				k = huff[0] + huff[1];
				sum = sum + k;
				huff[0] = k;
				huff[1] = Integer.MAX_VALUE;
				num--;
			}
			System.out.println(sum);
		}
	}
}