Huffman

#!/usr/bin/env python
# paulogp
# http://en.literateprograms.org/Huffman_coding_(Python)

def makeHuffTree(symbolTupleList):
    sortedList = list(symbolTupleList)
    sortedList.sort()

    from bisect import insort

    while len(sortedList) > 1:
        childL, childR = sortedList.pop(1), sortedList.pop(0)
        parent = (childL[0] + childR[0], childL, childR)
        insort(sortedList, parent)

    return sortedList[0]

def printHuffTree(huffTree, prefix = ''):
    if len(huffTree) == 2:
        print huffTree[1], prefix
    else:
        printHuffTree(huffTree[1], prefix + '0')
        printHuffTree(huffTree[2], prefix + '1')

# Exemplo
exampleData = [
    (0.124167  , 'e'),
    (0.0969225 , 't'),
    (0.0820011 , 'a'),
    (0.0768052 , 'i'),
    (0.0764055 , 'n'),
    (0.0714095 , 'o'),
    (0.0706768 , 's'),
    (0.0668132 , 'r'),
    (0.0448308 , 'l'),
    (0.0363709 , 'd'),
    (0.0350386 , 'h'),
    (0.0344391 , 'c'),
    (0.028777  , 'u'),
    (0.0281775 , 'm'),
    (0.0235145 , 'f'),
    (0.0203171 , 'p'),
    (0.0189182 , 'y'),
    (0.0181188 , 'g'),
    (0.0135225 , 'w'),
    (0.0124567 , 'v'),
    (0.0106581 , 'b'),
    (0.00393019, 'k'),
    (0.00219824, 'x'),
    (0.0019984 , 'j'),
    (0.0009325 , 'q'),
    (0.000599  , 'z')
]

if __name__ == '__main__':
    huffTree = makeHuffTree(exampleData)
    printHuffTree(huffTree)