Huffman Codeword Dictionary

Problem

Build a Huffman code table mapping each symbol to its codeword string. Repeatedly merge the two lightest subtrees from a min-heap keyed by weight and then creation order; the first popped subtree receives prefix 0 and the second receives prefix 1. Return an empty dictionary for no symbols and the single code 0 for one symbol.

Hint

Keep each subtree as a symbol-to-suffix dictionary and add one bit when merging.

Test cases

case 1

in: [["a","b","c"],[1,1,2]]

expected: {"c":"0","a":"10","b":"11"}

case 2

in: [["x"],[5]]

expected: {"x":"0"}

case 3

in: [[],[]]

expected: {}

case 4

in: [["a","b","c","d"],[1,1,1,1]]

expected: {"a":"00","b":"01","c":"10","d":"11"}

case 5

in: [["a","b","c","d","e"],[5,4,3,2,1]]

expected: {"c":"00","e":"010","d":"011","b":"10","a":"11"}

Starter codePython

import heapq
def huffman_code_table(symbols, freqs):
    # Your code here
    pass

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