求解哈夫曼编码问题（贪心）

### 关于哈夫曼编码的贪心算法解决方案

#### 构建哈夫曼树的过程

哈夫曼编码利用了贪心策略来构建最优前缀码。具体来说，在每次迭代过程中，选取频率最低的两个节点作为新内部节点的孩子，并将这两个节点从集合中移除，再把新的内部节点加入到集合中。重复此过程直到只剩下一个根节点为止[^1]。

对于给定的一组字符及其出现概率或频数：

- 创建一个叶子结点列表，其中每个元素代表一个字符以及其对应的权重（即该字符出现的概率或次数）
- 使用最小堆维护这些叶节点组成的优先级队列
- 不断取出当前具有最小权重的两个节点创建一个新的父节点，设置这个新节点的权重等于两子节点权重之和
- 将新建好的父节点重新放回优先级队列中继续参与后续的选择操作
- 当所有输入字符都被处理完毕之后，最终剩下的那个唯一节点就是整个哈夫曼树的根节点

#### 实现细节与复杂度分析

为了高效地完成上述流程中的选择最小权值的操作，通常会采用二叉堆这样的数据结构来表示优先队列。初始化阶段只需要线性扫描一遍所有的字符即可完成；而在每一轮合并时，由于涉及到插入和删除最小元素的动作，所以单次的时间开销是对数级别的 O(log n)，而总共有 n−1 次这样的合并动作发生，故整体时间复杂度为 O(n log n)[^3]。

以下是 Python 版本的具体实现代码示例:

import heapq
from collections import defaultdict, Counter


def huffman_encoding(data):
    frequency = dict(Counter(data))
    
    heap = [[weight, [symbol, ""]] for symbol, weight in frequency.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
            
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]

        heapq.heappush(heap, [lo[0]+hi[0]] + lo[1:] + hi[1:])
        
    return sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))

data = "this is an example for huffman encoding"
encoding = huffman_encoding(data)
print("Symbol".ljust(10) + "Frequency".ljust(10) + "Huffman Code")
for i in encoding:
    print(f"{i[0]}".ljust(10), end="")
    print(str(data.count(i[0])).ljust(10), end="")  
    print(i[1])