Huffman Average Code Length

Problem

Build a Huffman code from a list of frequencies and return its expected codeword length in bits:

L = sum(p_i * l_i), p_i = f_i / sum(f)

Use a min-heap keyed by frequency and then creation order for deterministic ties. A single symbol has length 1.

Hint

The Huffman average length is always within 1 bit of the entropy.

case 1

in: [[1,1]]

expected: 1

case 2

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

expected: 1.9

case 3

in: [[1,1,1]]

expected: 1.6666666666666665

case 4

in: [[5]]

expected: 1

case 5

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

expected: 2.2

Starter codePython

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

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