Huffman Code Lengths

Problem

Build a Huffman code for the given symbols and frequencies and return a dictionary mapping each symbol to its codeword length. Break ties by preferring the node created earlier, using a min-heap keyed by frequency and then creation order. A lone symbol is assigned length 1.

Hint

Repeatedly merge the two lightest nodes; each merge adds one bit to every leaf beneath it.

Test cases

case 1

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

expected: {"a":1,"b":1}

case 2

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

expected: {"d":1,"c":2,"a":3,"b":3}

case 3

in: [["x","y","z"],[1,1,1]]

expected: {"z":1,"x":2,"y":2}

case 4

in: [["solo"],[7]]

expected: {"solo":1}

case 5

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

expected: {"c":2,"e":3,"d":3,"b":2,"a":2}

Starter codePython

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

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