哈夫曼樹構建原則：
- .統計頻率：對待編碼字符（或數據塊）的頻率進行統計。
- .初始化森林：將每個字符視為一棵只有根節點的二叉樹，權值為頻率。
- .合并樹：重復以下操作，直到只剩一棵樹：
- 選取權值最小的兩棵樹合并，新樹的根節點權值為兩者之和。
- 權值較小的樹作為左子樹，較大的為右子樹（約定方向不影響結果）。
- 生成編碼：從根節點出發，向左子樹路徑標記
0，向右標記1，到葉子節點的路徑即為該字符的哈夫曼編碼。
?引用python模塊說明：
heapq.heapify?是?heapq?模塊（堆隊列算法）的核心函數，用于將普通列表原地轉換為最小堆數據結構。
import heapq# 原始未排序列表
data = [3, 1, 4, 1, 5, 9, 2, 6]
print("轉換前:", data) # [3, 1, 4, 1, 5, 9, 2, 6]# 原地轉換為最小堆
heapq.heapify(data)print("轉換后:", data) # 輸出可能: [1, 1, 2, 3, 5, 9, 4, 6]
print("最小元素:", data[0]) # 1 (始終是堆頂)圖示化：
? ? ? 1 ? ?← 堆頂 (最小元素)
? ? / ? \
? ?1 ? ? 2
? / \ ? / \
?3 ? 5 9 ? 4
/
6?
import heapqclass Node:def __init__(self, char=None, freq=0, left=None, right=None):self.char = char # 字符（僅葉子節點有）self.freq = freq # 頻率self.left = left # 左子節點self.right = right # 右子節點# 用于優先隊列比較def __lt__(self, other):return self.freq < other.freqdef build_huffman_tree(freq_dict):heap = [Node(char=char, freq=freq) for char, freq in freq_dict.items()]heapq.heapify(heap) # 轉為最小堆while len(heap) > 1:left = heapq.heappop(heap) # 彈出最小頻率節點right = heapq.heappop(heap) # 彈出次小頻率節點merged = Node(freq=left.freq + right.freq, left=left, right=right)heapq.heappush(heap, merged) # 合并后的樹放回堆中，繼續轉為最小堆return heap[0] # 返回哈夫曼樹的根節點def generate_codes(root, current_code="", code_dict={}):if root is None:returnif root.char is not None: # 葉子節點,則加入字典code_dict[root.char] = current_codegenerate_codes(root.left, current_code + "0", code_dict) #遞歸調用generate_codes(root.right, current_code + "1", code_dict) #遞歸調用return code_dict# 示例：壓縮字符串 "aabbbcd"
freq = {'a': 2, 'b': 3, 'c': 1, 'd': 1}
huffman_tree = build_huffman_tree(freq)
codes = generate_codes(huffman_tree)
print("哈夫曼編碼:", codes) # 輸出如 {'b': '0', 'a': '10', 'c': '110', 'd': '111'}
