Huffman Canonical Codes

Problem

Given symbol-frequency pairs, build a Huffman tree and return a dictionary of canonical prefix codes.

Merge the two lightest nodes, breaking ties deterministically by insertion order, then assign code lengths from the tree and hand out canonical codes sorted by length and then symbol. A single symbol gets the code 0 and no symbols gives an empty dictionary.

Hint

Canonical codes are assigned in order of increasing length, incrementing the previous code after shifting it.

Test cases

case 1

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

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

case 2

in: [[["a",1]]]

expected: {"a":"0"}

case 3

in: [[]]

expected: {}

case 4

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

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

case 5

in: [[["x",10],["y",5],["z",5],["w",1]]]

expected: {"x":"0","z":"10","w":"110","y":"111"}

Starter codePython

def huffman_canonical_codes(pairs):
    # Your code here
    pass

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