哈夫曼编码的实验代码 1. 初始化一个大小为n的优先队列（最小堆），并将所有字符及其频率插入队列。 2. 当队列的大小大于1时，执行以下操作： a. 从队列中删除两个最小频率的字符及其编码。 b. 将
进行n-1次插入和删除操作，所以总的时间复杂度为O((n-1)logn)。空间复杂度：优先队列的大小为n，所以空间复杂度为O(n)。
以下是哈夫曼编码的实验代码：
```python
import heapq
from collections import defaultdict
def huffman_encoding(s):
# 统计字符频率
freq = defaultdict(int)
for c in s:
freq[c] += 1
# 初始化优先队列（最小堆）
min_heap = [[weight, [char, ""]] for char, weight in freq.items()]
heapq.heapify(min_heap)
# 构建哈夫曼树
while len(min_heap) > 1:
lo = heapq.heappop(min_heap)
hi = heapq.heappop(min_heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(min_heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
# 提取哈夫曼编码
huff_dict = dict(heapq.heappop(min_heap)[1:])
encoded_str = "".join(huff_dict[c] for c in s)
return huff_dict, encoded_str
# 测试
s = "this is an example for huffman encoding"
huff_dict, encoded_str = huffman_encoding(s)
print("哈夫曼编码字典：", huff_dict)
print("编码后的字符串：", encoded_str)
```
注意：这个代码示例仅适用于给定的输入字符串，如果需要处理其他字符串，请将`s`替换为相应的输入。
以下是哈夫曼编码的实验代码：
```python
import heapq
from collections import defaultdict
def huffman_encoding(s):
# 统计字符频率
freq = defaultdict(int)
for c in s:
freq[c] += 1
# 初始化优先队列（最小堆）
min_heap = [[weight, [char, ""]] for char, weight in freq.items()]
heapq.heapify(min_heap)
# 构建哈夫曼树
while len(min_heap) > 1:
lo = heapq.heappop(min_heap)
hi = heapq.heappop(min_heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(min_heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
# 提取哈夫曼编码
huff_dict = dict(heapq.heappop(min_heap)[1:])
encoded_str = "".join(huff_dict[c] for c in s)
return huff_dict, encoded_str
# 测试
s = "this is an example for huffman encoding"
huff_dict, encoded_str = huffman_encoding(s)
print("哈夫曼编码字典：", huff_dict)
print("编码后的字符串：", encoded_str)
```
注意：这个代码示例仅适用于给定的输入字符串，如果需要处理其他字符串，请将`s`替换为相应的输入。
