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 nodeCompute 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.
- Output the minimum sum of external path length.
1 2 3
1 1 3 5
- 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.