OpenJudge

3:Huffman coding tree

总时间限制:
1000ms
内存限制:
65535kB
描述

Construct an expanded binary tree with nexternal nodes, each external node Ki related to a weight Wi, which minimizes thesum of the external path length of leaf:  

                     Min( W1 * L1 + W2 * L2 + W3 * L3 + … + Wn * Ln)

Wi: the weight of each node

Li: the path length betweenthe root and the ith external node

Compute to minimize the sum of the external path length


输入
The first line is an integer t, which represents the number of groups of the test data.
For each group data, the first line is an integer n. n represents the number of external nodes. Input n integers in the second line, which represent the weight of each external node.
2<=N<=100
输出
Output the minimum sum of external path length.
样例输入
2
3
1 2 3
4
1 1 3 5
样例输出
9
17
提示
Only test your ability to build Huffman coding tree, with small data sets. It is optional for you to use heap. However, encourage you to use the heap implemented in the first question to search the smallest and second smallest element.
全局题号
5941
提交次数
430
尝试人数
180
通过人数
179

Other language verions