贪心算法的高逼格应用——Huffman编码

import sys
 
 
# Huffman节点类
class HuffmanNode:
    def __init__(self, weight=0, parent=-1, left_child=-1, right_child=-1, value=""):
        # 权重
        self.weight = weight
        # 父节点索引
        self.parent = parent
        # 左孩子节点索引
        self.left_child = left_child
        # 右孩子节点索引
        self.right_child = right_child
        # 代表的字符
        self.value = value
 
    def __str__(self):
        return "weight:{}, parent:{}, left_child:{}, right_child:{}, value:{}".format(self.weight, self.parent, self.left_child, self.right_child, self.value)
 
 
# 构造Huffman树
def huffman_tree(nodes, num):
    # 需要构建的非叶子节点有N-1个,均排在节点数组后面,故须循环N-1次
    for i in range(num-1):
        # 最小的两个权值,这里m1小于等于m2
        m1 = m2 = sys.maxsize
        # 最小权值节点对应的索引
        x1 = x2 = -1
        # 循环当前所有可用的节点
        for j in range(num + i):
            if(nodes[j].weight < m1 and nodes[j].parent==-1):
                m2 = m1
                x2 = x1
                m1 = nodes[j].weight
                x1 = j
            elif(nodes[j].weight < m2 and nodes[j].parent==-1):
                m2 = nodes[j].weight
                x2 = j
        # 给需要合并成树的子节点设置父节点索引
        nodes[x1].parent = num + i
        nodes[x2].parent = num + i
        # 给合并成树的父节点设置子节点信息
        nodes[num + i].left_child = x1
        nodes[num + i].right_child = x2
        nodes[num + i].weight = m1 + m2
 
 
# 通过Huffman树获得Huffman编码
def huffman_code(nodes, num):
    # 最终结果
    huff_codes = dict()
    # 循环所有的叶子节点,叶子节点都在节点数组前面
    for i in range(num):
        # 该叶子节点对应的编码数组
        leaf_code = []
        # 当前节点索引
        c = i
        # 父节点索引
        p = nodes[i].parent
        while p != -1:
            # 当前节点是父节点的左孩子,编码为0,当前节点是父节点的右孩子,编码为1
            if nodes[p].left_child == c:
                leaf_code.insert(0, 0)
            elif nodes[p].right_child == c:
                leaf_code.insert(0, 1)
            # 将当前节点和父节点沿路径上移
            c = p
            p = nodes[c].parent
        
        if len(leaf_code)>0:
            huff_codes[nodes[i].value] = "".join(str(lc) for lc in leaf_code)
    return huff_codes
 
 
# 算法主体
def run():
    N = 6
    # 初始化节点数组,对N个元素进行编码,则Huffman树的节点数是2N-1
    nodes = [HuffmanNode() for _ in range(2*N - 1)]
    # 初始化叶子节点
    nodes[0].weight = 5
    nodes[0].value = "a"
    nodes[1].weight = 32
    nodes[1].value = "b"
    nodes[2].weight = 18
    nodes[2].value = "c"
    nodes[3].weight = 7
    nodes[3].value = "d"
    nodes[4].weight = 25
    nodes[4].value = "e"
    nodes[5].weight = 13
    nodes[5].value = "f"
    # 构建Huffman树 
    huffman_tree(nodes, N)
    # 从Huffman树中获得叶子节点的Huffman编码
    result = huffman_code(nodes, N)
    
    for r in result:
        print("{} 的 Huffman编码是:{}".format(r, result[r]))
 
 
if __name__ == "__main__":
    run()