CODEWITHSUNDEEP
algorithmoptimizationbinary-tree
user18917702
user18917702

Reputation:

Algorithm to minimise the sum of products of leaf values and their depth

I'm stuck with a computer science problem I'm trying to solve. Suppose you have a binary tree (which does not need to be balanced), where each node has at most two child nodes and where only a leaf can contain an integer value (the root and the middle nodes do not). We are given an array of values and have to construct such a tree with the constraint:

𝐷𝑚 = min ∑𝑛𝑖=1 𝐴𝑖 𝑑𝑖

Where 𝐴𝑖 is the value of the array element 𝑖 and 𝑑𝑖 is the depth of that element. The sum of these products should be minimised.

How do I write an algorithm with the runtime 𝑛log(𝑛) that constructs such a tree?

Upvotes: 2

Views: 142

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59253

As @user3386109 suggests in comments, this is exactly the problem of finding an optimal prefix-free code for a set of symbols given their counts.

Huffman Coding is simple, and known to be optimal:

  • Start with a singleton tree for each value
  • Repeatedly join the two trees with the smallest total value, until you have only one tree left.

To prove this is optimal, consider that:

  • No matter what the shape of your tree is, the deepest level will always contain at least 2 leaves that share a parent
  • It would be optimal to assign the smallest two values to those leaves

Therefore, joining the smallest two values is always an optimal decision. The remainder of the connections can then be made by solving a smaller instance of the same problem:

Let's say that you join values a and b. The the cost of placing the new parent at depth d then becomes (a+b)*(d+1) = d(a+b) + a + b. The constant a+b can then be subtracted from all possible solutions.

Upvotes: 1

Related Questions