Problem Description

Huffman trees are widely used in encoding applications. This problem focuses only on the construction process of a Huffman tree.

Given a sequence of numbers {pi} = {p0, p1, …, pn-1}, the process to construct a Huffman tree is as follows:

1. Find the two smallest numbers in {pi}, denote them as pa and pb. Remove pa and pb from {pi}, then add their sum back to {pi}. The cost of this operation is pa + pb.
2. Repeat step 1 until only one number remains in {pi}.

The total cost of constructing the Huffman tree is the sum of all costs incurred during the above operations.

Task: Given a sequence of numbers, calculate the total cost of constructing a Huffman tree using these numbers.

Example

For the sequence {pi} = {5, 3, 8, 2, 9}, the construction process is:

1. Find the two smallest numbers in {5, 3, 8, 2, 9}, wich are 2 and 3. Remove them and add their sum 5. The set becomes {5, 8, 9, 5}, with a cost of 5.
2. Find the two smallest numbers in {5, 8, 9, 5}, which are 5 and 5. Remove them and add their sum 10. The set becomes {8, 9, 10}, with a cost of 10.
3. Find the two smallest numbers in {8, 9, 10}, which are 8 and 9. Remove them and add their sum 17. The set becomes {10, 17}, with a cost of 17.
4. Find the two smallest numbers in {10, 17}, which are 10 and 17. Remove them and add their sum 27. The set becomes {27}, with a cost of 27.
5. Only one number remains. The construction ends. Total cost = 5 + 10 + 17 + 27 = 59.

Input Format

The first line contains a positive integer n (n ≤ 100).

The next line contains n positive integers representing p0, p1, …, pn-1, each not exceeding 1000.

Output Format

Output the total cost of constructing the Huffman tree.

Sample Input

5
5 3 8 2 9

Sample Output

59

Solution Approach

Method 1: Recursive Implementation

This approach uses a recursive funcsion that repeatedly finds the two smallest elements, combines them, and accumulates the cost.

def calculate_huffman_cost(numbers):
    if len(numbers) < 2:
        return 0
    
    numbers.sort()
    first = numbers.pop(0)
    second = numbers.pop(0)
    combined = first + second
    numbers.append(combined)
    
    return combined + calculate_huffman_cost(numbers)

count = int(input())
values = [int(x) for x in input().split()]
result = calculate_huffman_cost(values)
print(result)

Method 2: Iterative Implementation with Sorted List

This approach uses an iterative loop with sorting at each step to find the two smallest elements.

def compute_tree_cost(elements):
    total = 0
    while len(elements) > 1:
        elements.sort()
        smallest = elements[0]
        next_smallest = elements[1]
        merged = smallest + next_smallest
        total += merged
        elements = elements[2:]
        elements.append(merged)
    return total

n = int(input())
data = [int(x) for x in input().split()]
print(compute_tree_cost(data))

Complexity Analysis

Both solutions have a time complxeity of O(n² log n) due to repeated sorting operations. The space complexity is O(n) for storing the intermediate results.