不使用优先队列构建霍夫曼树的实用算法详解

import collections

# 定义霍夫曼树的节点
class HuffmanNode:
    def __init__(self, char, freq, left=None, right=None):
        self.char = char  # 字符 (对于内部节点为None)
        self.freq = freq  # 频率
        self.left = left  # 左子节点
        self.right = right # 右子节点

    # 用于比较节点，以便排序
    def __lt__(self, other):
        return self.freq < other.freq

    def __repr__(self):
        return f"Node(char='{self.char}', freq={self.freq})"

def build_huffman_tree_without_priority_queue(text):
    """
    不使用优先队列构建霍夫曼树。
    """
    if not text:
        return None

    # 1. 计算字符频率
    frequency = collections.Counter(text)

    # 2. 初始化叶子节点列表并排序
    # list_symbols 存储原始字符节点，按频率升序排列
    list_symbols = sorted([HuffmanNode(char, freq) for char, freq in frequency.items()])

    # 3. 创建空的合并节点列表
    # list_combined 存储合并后的内部节点，也保持按频率升序排列
    list_combined = []

    # 辅助函数：从两个列表中选择频率最小的节点并移除
    def get_min_node():
        node1 = list_symbols[0] if list_symbols else None
        node2 = list_combined[0] if list_combined else None

        if node1 and (not node2 or node1.freq < node2.freq):
            return list_symbols.pop(0)
        elif node2 and (not node1 or node2.freq <= node1.freq):
            return list_combined.pop(0)
        else:
            return None # 理论上不会发生，除非两个列表都为空

    # 4. 迭代合并，直到只剩一个根节点
    while len(list_symbols) + len(list_combined) > 1:
        # 选择频率最小的两个节点
        node1 = get_min_node()
        node2 = get_min_node()

        if not node1 or not node2: # 异常情况处理
            break

        # 创建新的父节点
        merged_freq = node1.freq + node2.freq
        parent_node = HuffmanNode(None, merged_freq, node1, node2)

        # 将新父节点添加到 list_combined 的末尾
        # 由于其频率总是大于或等于 list_combined 中现有节点，
        # list_combined 依然保持升序
        list_combined.append(parent_node)

    # 最终剩下的节点就是霍夫曼树的根
    if list_symbols:
        return list_symbols[0]
    elif list_combined:
        return list_combined[0]
    else:
        return None # 空文本情况

# 辅助函数：生成霍夫曼编码
def generate_huffman_codes(root, current_code="", codes={}):
    if root is None:
        return

    if root.char is not None: # 叶子节点
        codes[root.char] = current_code
        return

    generate_huffman_codes(root.left, current_code + "0", codes)
    generate_huffman_codes(root.right, current_code + "1", codes)
    return codes

# 测试
if __name__ == "__main__":
    test_text = "this is an example of a huffman tree"
    print(f"原始文本: {test_text}")

    huffman_root = build_huffman_tree_without_priority_queue(test_text)

    if huffman_root:
        huffman_codes = generate_huffman_codes(huffman_root)
        print("\n霍夫曼编码:")
        for char, code in sorted(huffman_codes.items()):
            print(f"'{char}': {code}")
    else:
        print("无法构建霍夫曼树，文本为空。")

    # 另一个例子
    test_text_2 = "aaaaabbbbcccdde"
    print(f"\n原始文本: {test_text_2}")
    huffman_root_2 = build_huffman_tree_without_priority_queue(test_text_2)
    if huffman_root_2:
        huffman_codes_2 = generate_huffman_codes(huffman_root_2)
        print("\n霍夫曼编码:")
        for char, code in sorted(huffman_codes_2.items()):
            print(f"'{char}': {code}")