Huffman Length Variance

Problem

Build a Huffman code from a list of frequencies using a min-heap keyed by frequency and then creation order, and return the variance of the codeword lengths under the frequency distribution. The variance is E[l^2] - (E[l])^2 where each symbol is weighted by its normalized frequency. Return 0.0 for fewer than two symbols.

Hint

All codeword lengths are equal only for a uniform distribution on a power-of-two alphabet.

Test cases

case 1

in: [[1,1,1,1]]

expected: 0

case 2

in: [[5,2,1]]

expected: 0.234375

case 3

in: [[1,1]]

expected: 0

case 4

in: [[3,3,3,1,1]]

expected: 0.14876033057851237

Starter codePython

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

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