Huffman Entropy Gap

Problem

Return the gap in bits between the expected Huffman codeword length and the source entropy, L - H(freqs). Build the Huffman lengths with a min-heap keyed by frequency and then creation order, and compute H over the normalized frequencies. Return 0.0 for fewer than two symbols and clamp tiny negative floating-point noise to 0.0.

Hint

The expected Huffman length is always at least the entropy, and the gap is below one bit.

Test cases

case 1

in: [[1,1]]

expected: 0

case 2

in: [[5,2,1]]

expected: 0.07620505930460153

case 3

in: [[4,1]]

expected: 0.2780719051126377

case 4

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

expected: 0.019174063770921457

Starter codePython

import heapq, math
def huffman_entropy_gap(freqs):
    # Your code here
    pass

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