哈夫曼树构建必须用小顶堆优先队列，不能用vector排序模拟；节点须用指针存储并统一释放内存；编码生成必须DFS递归，传值拼接字符串；需处理空树、单字符等边界情况。
哈夫曼树构建必须用优先队列，不能用普通vector排序模拟
手动维护一个 std::vector 并每次 sort() 插入新节点，时间复杂度会退化到 O(n² log n)，而标准实现应是 O(n log n)。核心在于：每次只取权重最小的两个节点合并，天然适配 std::priority_queue 的堆结构。
注意默认 std::priority_queue<int></int> 是大顶堆，哈夫曼需要小顶堆，必须显式指定比较器：
struct Node {
int weight;
Node* left, *right;
Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};
auto cmp = [](Node* a, Node* b) { return a->weight > b->weight; };
std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> pq(cmp);
- 漏写比较器会导致取到最大权重节点，结果完全错误
- 不要存
Node值对象进队列——必须用指针，否则合并后原节点被拷贝，父子关系断裂 - 所有动态分配的
Node*必须在最后统一delete，否则内存泄漏
编码生成必须用DFS递归或栈模拟，不能靠父指针逆推
哈夫曼编码本质是根到叶的路径（左0右1），最可靠方式是从根出发 DFS 遍历，边走边拼接编码字符串。有人试图给每个节点加 parent 指针再从叶子往上回溯，但这样需额外存储、易空指针崩溃，且无法保证编码位序正确（谁左谁右必须由建树时决定）。
DFS 实现要点：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
void generateCodes(Node* root, std::string code,
std::unordered_map<char, std::string>& codes) {
if (!root) return;
if (!root->left && !root->right) { // 叶子节点
codes[root->ch] = code; // 假设 Node 存了字符 ch
return;
}
generateCodes(root->left, code + "0", codes);
generateCodes(root->right, code + "1", codes);
}
- 必须判断
!root->left && !root->right才算叶子，仅靠weight == 1或字符存在性都不安全 - 传入
code要用值传递，不是引用——否则多个分支会相互污染 - 若输入含重复字符（如多个 'a'），需先统计频次再建叶节点，不能按字符 ASCII 建树
贪心选择性质在这里成立，但只适用于“前缀码”场景
哈夫曼算法的贪心策略（每步合并最小两频次节点）能得全局最优，前提是目标函数是总加权路径长 Σ(freq[i] × len(code[i])) 最小，且编码必须是前缀码（无码字是另一码字前缀）。这点常被忽略：
- 如果允许非前缀码（比如用终止符分隔），可能更短——但解码不唯一，实际不可用
- 若字符频率分布极偏（如一个字符占 99%），哈夫曼仍最优，但和等长编码差距不大；此时压缩收益低，但算法本身没错
- 浮点频率或负权重会直接破坏贪心前提，
weight必须是非负整数
实际编码输出要处理空树、单字符等边界情况
真实数据中可能出现：空字符串、只有一种字符、所有字符频次为 0。这些情况不处理，priority_queue 会空 pop 或 DFS 进入无限递归。
- 建树前检查
pq.size() == 0→ 返回空编码表 -
pq.size() == 1时不能执行合并循环，必须手动设该节点编码为"0"（或"1"，但惯例用"0"） - 频次为 0 的字符应直接过滤，否则会生成无效叶节点干扰树形
- 输出编码表时建议按字符 ASCII 排序打印，方便人工核对，而非按插入顺序
最易被忽略的是单字符情形——此时没有“合并”动作，根就是叶子，但很多实现直接从合并循环出来就调用 DFS，导致访问空指针。这个分支必须单独兜底。
