项目开发求助：如何不使用priority queues实现Huffman Tree？

问题背景 #

我正在开展一个Huffman Tree项目，但讲师要求不得使用优先队列来构建该树，不清楚具体实现方式，请问是否存在其他实现Huffman Tree的方法？
注：原提问附带了3张使用优先队列实现Huffman树的示例图

可行的替代实现方法 #

1. 线性扫描查找最小节点 #

这是最直观的替代方案，不需要任何复杂数据结构，核心是每次遍历节点集合找最小的两个元素：

• 步骤：
  1. 将所有带权重的字符初始化为独立的树节点，存入一个列表/数组中
  2. 当列表内节点数量大于1时：
     • 遍历列表，找到权重最小的节点A，从列表中移除
     • 再次遍历列表，找到权重最小的节点B，从列表中移除
     • 创建新的父节点，权重为A与B的权重之和，将A、B设为该节点的左右子节点
     • 将新父节点加入列表
  3. 列表中最后剩余的节点即为Huffman树的根节点
• 优缺点：逻辑简单易实现，无需额外依赖；但时间复杂度为O(n²)，仅适合小规模数据场景

2. 预排序+归并式合并 #

利用排序后的有序集合，通过类似归并排序的思路高效合并节点：

• 步骤：
  1. 将所有叶子节点按权重升序排序，存入数组S
  2. 维护一个临时数组M，用于存储合并后的中间节点，始终保持M按权重升序排列
  3. 每次从S和M的头部取出权重最小的两个节点（因两个数组均有序，只需比较两个数组的首元素）
  4. 合并这两个节点得到新节点，将新节点插入M的对应位置以维持有序性
  5. 重复步骤3-4，直到S和M中仅剩一个节点
• 优缺点：时间复杂度由排序环节主导，为O(n log n)，效率接近优先队列实现；需要维护两个有序集合，实现难度略高于线性扫描

3. 二叉搜索树（BST）维护节点集合 #

用BST存储所有节点，以权重作为排序键，快速获取最小节点：

• 步骤：
  1. 将所有叶子节点插入BST，节点按权重大小排序
  2. 当BST中节点数量大于1时：
     • 取出BST中权重最小的两个节点（即两次获取BST的最左子节点）
     • 合并得到新节点，将新节点插入BST的合适位置以维持树的有序性
  3. 最终BST的根节点即为Huffman树的根
• 优缺点：查找、删除、插入操作的平均时间复杂度为O(log n)，整体效率较高；但手动实现平衡BST（如AVL树、红黑树）以避免最坏情况的O(n)复杂度，会增加代码复杂度

内容的提问来源于stack exchange，提问作者Grant Sodipo