ハフマンツリー(Python実装)

"""
【    】        Huffman    ，      ，           ，
                         ，    。
                     ，            Huffman         。
【    】                  。
【    】     Huffman  。
"""
import numpy as np


class node:  #    ：  ，  ，    
    def __init__(self, name=None, value=None):
        self._name = name
        self._value = value
        self._left = None
        self._right = None


class huff_man_tree:
    """
           ，        ，        ：
    1、      ；    ，  
    2、                
    3、         ，       （        ）
    4、    ，      
    5、               
    """
    def __init__(self, char_weights):
        self.a = [node(part[0], part[1]) for part in char_weights]  #       
        while len(self.a) != 1:
            self.a.sort(key=lambda node: node._value, reverse=True)  #            
            c = node(value=(self.a[-1]._value + self.a[-2]._value))
            c._left = self.a.pop(-1)
            c._right = self.a.pop(-1)
            self.a.append(c)
        self.root = self.a[0]
        self.b = np.zeros(self.root.__sizeof__(), dtype=np.int)  # self.b                

    """
             ，      ，    0，    1，          、        。
    """

    def set_code(self, tree, length, code):
        node = tree
        s = ""
        if not node:
            return
        elif node._name:
            for i in range(length):
                s = s + str(self.b[i])
            code[node._name] = s  #        
            return
        self.b[length] = 0
        self.set_code(node._left, length + 1, code)  #      
        self.b[length] = 1
        self.set_code(node._right, length + 1, code)  #      

    """
           ，              ，         
    """
    def get_code(self):
        code = {
     }
        self.set_code(self.root, 0, code)
        code_name = sorted(code, key=lambda code: code[0])  #              
        for temp in code_name:
            print(temp, end=' ')
            print(code.get(temp))


def main():
    """
    【    】
     6
     45 13 12 16 9 5
    """
    ch = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n']
    char_weights = []
    n = int(input())
    weight = [int(i) for i in input().split()]
    for i in range(n):
        char_weights.append((ch[i], weight[i]))  #      
    """
    【    】
    a 0
    b 101
    c 100
    d 111
    e 1101
    f 1100
    """
    tree = huff_man_tree(char_weights)
    tree.get_code()
    """
    【    】
       ：     6，a f          ：45, 13, 12, 16, 9, 5。
       ：       Huffman  。
    """


if __name__ == '__main__':
    main()