不使用优先队列构建哈夫曼树的技巧-java教程-PHP中文网

不使用优先队列构建哈夫曼树的技巧

心靈之曲

发布： 2025-10-05 12:02:19

原创

687人浏览过

不使用优先队列构建哈夫曼树的技巧

本文介绍了一种在不使用优先队列的情况下构建哈夫曼树的实用技巧。该方法通过维护两个有序列表，避免了频繁的查找最小元素的开销，从而高效地构建哈夫曼树。适用于需要避免使用优先队列的特定场景，例如教学或资源受限的环境。

哈夫曼树是一种用于数据压缩的树形结构，其构建过程通常涉及优先队列，以便高效地找到具有最小权重的节点。然而，在某些情况下，例如教学或资源受限的环境，可能需要避免使用优先队列。本文介绍一种巧妙的方法，可以在不使用优先队列的情况下构建哈夫曼树。

构建哈夫曼树的替代方法

该方法的核心思想是维护两个有序列表：

初始列表： 包含所有符号及其概率，并按概率升序排列。
合并列表： 初始为空，用于存放合并后的符号，并始终保持升序排列。

构建哈夫曼树的步骤如下：

Smart Picture

Smart Picture 智能高效的图片处理工具

查看详情

初始化： 创建初始列表，并按概率升序排列。创建空的合并列表。
迭代合并： 当列表中的符号数量大于 1 时，重复以下步骤：
1. 从初始列表和合并列表的开头移除两个最小的符号。
2. 将这两个符号合并为一个新的符号，其概率为两个符号的概率之和。
3. 将新的符号添加到合并列表的末尾。由于新的符号的概率大于之前合并的任何符号，因此合并列表仍然保持有序。
完成： 当列表中只剩下一个符号时，哈夫曼树构建完成。

示例代码（Python）

以下是一个使用 Python 实现的示例代码：

def build_huffman_tree_without_priority_queue(symbols_with_probabilities):
    """
    构建哈夫曼树，不使用优先队列。

    Args:
        symbols_with_probabilities: 一个列表，包含符号及其概率，例如 [(symbol1, prob1), (symbol2, prob2), ...]

    Returns:
        哈夫曼树的根节点。
    """

    # 1. 创建初始列表并排序
    initial_list = sorted(symbols_with_probabilities, key=lambda x: x[1])
    combined_list = []

    # 2. 迭代合并
    while len(initial_list) + len(combined_list) > 1:
        # 2.1 确定要合并的两个最小符号
        if not initial_list:
            smallest1 = combined_list.pop(0)
            smallest2 = combined_list.pop(0)
        elif not combined_list:
            smallest1 = initial_list.pop(0)
            smallest2 = initial_list.pop(0)
        else:
            if initial_list[0][1] <= combined_list[0][1]:
                smallest1 = initial_list.pop(0)
                if not initial_list:
                    smallest2 = combined_list.pop(0)
                elif initial_list[0][1] <= combined_list[0][1]:
                     smallest2 = initial_list.pop(0)
                else:
                    smallest2 = combined_list.pop(0)
            else:
                smallest1 = combined_list.pop(0)
                if not combined_list:
                    smallest2 = initial_list.pop(0)
                elif initial_list[0][1] <= combined_list[0][1]:
                     smallest2 = initial_list.pop(0)
                else:
                    smallest2 = combined_list.pop(0)


        # 2.2 合并符号
        combined_probability = smallest1[1] + smallest2[1]
        combined_symbol = (smallest1, smallest2)  # 使用元组表示合并后的节点

        # 2.3 将合并后的符号添加到合并列表
        # 保持合并列表的有序性
        inserted = False
        for i in range(len(combined_list)):
            if combined_probability <= combined_list[i][1]:
                combined_list.insert(i, (combined_symbol, combined_probability))
                inserted = True
                break
        if not inserted:
            combined_list.append((combined_symbol, combined_probability))

    # 3. 返回哈夫曼树的根节点
    if initial_list:
        return initial_list[0]
    else:
        return combined_list[0]

# 示例用法
symbols = [('A', 0.1), ('B', 0.2), ('C', 0.4), ('D', 0.3)]
huffman_tree = build_huffman_tree_without_priority_queue(symbols)

print(huffman_tree) # 输出哈夫曼树的根节点

登录后复制

代码解释：