Huffman Tree Total Cost

Problem

Build a Huffman code for the given frequencies and return its total cost sum(f_i * l_i) in bits, where l_i is the codeword length of the i-th frequency. A useful identity: for two or more symbols the total cost equals the sum of all merged node weights during the bottom-up merge. Break ties with a min-heap keyed by weight and creation order. A single symbol gets codeword length 1.

Hint

Every merge charges the combined weight to every leaf beneath it.

Test cases

case 1

in: [[1,1]]

expected: 2

case 2

in: [[1,2,3,4]]

expected: 19

case 3

in: [[1,1,1]]

expected: 5

case 4

in: [[7]]

expected: 7

case 5

in: [[5,4,3,2,1]]

expected: 33

Starter codePython

import heapq
def huffman_total_cost(freqs):
    # Your code here
    pass

5 test cases · run your code against them in the editor