Minimizing sum of recursive pairwise sums

Question

What is the best algorithm for this?

We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at a time. The cost of each addition is the sum of the two integers, and this sum adds up cumulatively. After each addition, the two integers are removed from the array, but their sum is added, until only one value remains.

I think I have figured out so far that the optimal solution is to add up the two smallest values in the array at every step (as the earlier the figure is used the more times it is included in the cumulative cost.) Perhaps there is another way to think about the problem, though.

Is there some mathematical fact that trivializes the solution perhaps?

Example A:

Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

Example B:

Input: [1, 1, 1, 1, 1]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 1, 1, 2]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 2, 2]
Adding 1 and 2 together (Cost 1+2 = 3)
State: [2, 3]
Adding 2 and 3 together (Cost 2+3 = 5)
State: [5]
Total cost: 2 + 2 + 3 + 5 = 12

(I made these examples up myself; let me know if the examples are not actually the optimal solutions, although I am pretty confident they are.)

Answer 1

This problem can be solved using a min heap. You have to construct a min heap initially with all the elements of array. Now you simply take the top element of this heap and add it to the next top element of heap. Then reinsert the sum obtained in the heap. Keep a variable to track the total cost. This will ensure that you are adding the minimum elements and the final cost is minimum. This is analogous to the problem of connecting n ropes with minimum cost.