import heapq                     # 堆模块，用于快速取最小元素
from collections import Counter  # 计数器，统计字符出现次数

class HuffmanNode:
    """哈夫曼树的节点类"""
    def __init__(self, char, freq):
        self.char = char          # 字符（叶子节点才有值，内部节点为None）
        self.freq = freq          # 频次（权值）
        self.left = None          # 左孩子
        self.right = None         # 右孩子
    
    def __lt__(self, other):
        # 定义节点的比较方式，让堆可以按 freq 排序（小于号）
        return self.freq < other.freq

def build_huffman_tree(text):
    """根据文本构建哈夫曼树，返回根节点"""
    # 统计每个字符的出现次数
    freq_dict = Counter(text)
    # 创建优先队列（最小堆），每个节点初始就是叶子节点
    heap = [HuffmanNode(char, freq) for char, freq in freq_dict.items()]
    heapq.heapify(heap)   # 将列表转换为堆，保证堆顶是最小元素
    
    # 反复合并最小的两个节点，直到堆里只剩一个节点（即树根）
    while len(heap) > 1:
        left = heapq.heappop(heap)   # 弹出当前最小的（左孩子）
        right = heapq.heappop(heap)  # 弹出第二小的（右孩子）
        # 创建一个新节点作为它们的父节点，权值为两者之和
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)  # 把新节点放回堆中
    
    # 堆里剩下的唯一节点就是树根
    return heap[0] if heap else None

def generate_codes(root, code="", codes=None):
    """递归生成每个字符的哈夫曼编码，存入字典 codes 中"""
    if codes is None:
        codes = {}
    if root is not None:
        if root.char is not None:   # 叶子节点：找到了一个字符
            codes[root.char] = code
        else:                       # 内部节点：继续向左和右递归
            # 向左走加“0”，向右走加“1”
            generate_codes(root.left, code + "0", codes)
            generate_codes(root.right, code + "1", codes)
    return codes

def main():
    """主程序：演示哈夫曼树构建与编码"""
    text = "abracadabra"
    print("原始文本:", text)
    
    # 构建哈夫曼树
    root = build_huffman_tree(text)
    if root is None:
        print("文本为空，无法构建")
        return
    
    # 生成编码字典
    codes = generate_codes(root)
    
    # 按编码长度排序输出（短的在前）
    print("\n字符及其哈夫曼编码（按长度排序）：")
    for char, code in sorted(codes.items(), key=lambda x: len(x[1])):
        print(f"  '{char}' : {code}")
    
    # 计算压缩效果
    original_bits = len(text) * 8   # 假设原始每个字符用 8 位（ASCII）
    compressed_bits = sum(len(codes[ch]) for ch in text)
    print("\n原始大小（位）:", original_bits)
    print("哈夫曼压缩后大小（位）:", compressed_bits)
    print("节省了", original_bits - compressed_bits, "位！")

if __name__ == "__main__":
    main()

原始文本: abracadabra

字符及其哈夫曼编码（按长度排序）：
  'a' : 0
  'b' : 10
  'r' : 110
  'c' : 1110
  'd' : 1111

原始大小（位）: 88
哈夫曼压缩后大小（位）: 29
节省了 59 位！