哈夫曼树必须用小顶堆，因需反复取最小频次节点；C++ priority_queue 默认大顶堆，故需自定义比较器返回 a->freq > b->freq；节点宜用 vector 统一管理生命周期，避免内存泄漏；generateCodes 须传 string 引用并回溯，防重复拷贝与前缀污染；浮点频率应转整数以防精度误差。
为什么 priority_queue 必须用小顶堆，且自定义比较要反着写？
哈夫曼树构建的本质是反复合并频率最小的两个节点——这直接决定了必须用小顶堆（最小堆）来快速取最小。C++ 的 std::priority_queue 默认是大顶堆，所以必须显式指定容器和比较器：std::priority_queue<node std::vector>, Compare></node>，其中 Compare 要返回 true 当第一个参数「应该排在后面」，也就是 a->freq > b->freq。写成 就会变成大顶堆，导致每次取出来的是最大频次节点，整个贪心逻辑崩塌。
常见错误现象：priority_queue 构建出的树深度严重失衡，编码长度远非最优，甚至出现高频字符编码比低频还长。
- 务必用
std::greater<int></int>不适用于指针节点，必须手写仿函数或 lambda（C++11+） - 比较器捕获的是指针，比较的是
->freq，不是对象本身 - 插入前确认所有叶节点
freq > 0，否则 0 频次节点可能被优先合并，污染结果
如何安全地构建哈夫曼树并避免内存泄漏？
哈夫曼树节点通常动态分配，但合并过程中会产生大量中间节点。若仅靠裸指针管理，极易漏删或重复释放。推荐统一用智能指针，或更轻量的做法：把所有节点（包括合并生成的）存进一个 std::vector<:unique_ptr>></:unique_ptr>，最后由 vector 管理生命周期。
关键点在于：合并两个节点时，**不 delete 原节点，而是让它们成为新节点的左右子，然后将新节点 push_back 到容器中**。最终树根就是容器里最后一个元素，其余节点通过父子关系自然可达，无需单独释放。
立即学习“C++免费学习笔记（深入）”；
- 不要在
while (pq.size() > 1)循环里用new Node后裸存入 priority_queue —— 无法回收 - 如果坚持裸指针，必须在构建完成后递归遍历释放；但哈夫曼树无环、单根，可用栈模拟后序遍历释放
- 注意：叶节点（原始字符）可复用原数据，不必深拷贝；内部节点的
ch字段可设为 '\0' 标识
generateCodes() 递归生成编码时，为什么传引用比传值快且安全？
编码字符串在递归下降过程中不断拼接（如 code += "0"），若按值传递 std::string，每层调用都会触发复制，时间复杂度退化为 O(L²)，L 是路径长度。而传引用 + 回溯（push_back/pop_back）是标准解法。
示例核心片段：
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;
return;
}
code += '0';
generateCodes(root->left, code, codes);
code.pop_back(); // 回溯
code += '1';
generateCodes(root->right, code, codes);
code.pop_back();
}
- 传
std::string&是必须的，否则编码结果全为空串 -
pop_back()不可省略，否则右子树会继承左子树的 code 前缀 - 若字符集含
\0或非 ASCII，ch类型建议用int或unsigned char，避免符号扩展问题
输入频率为浮点数或归一化概率时，为什么要转成整数频次？
哈夫曼算法理论支持实数权重，但实际实现中，priority_queue 对浮点比较存在精度误差风险（尤其当多个频率非常接近时），可能导致合并顺序错乱。更根本的是：编码长度只取决于相对大小关系，而非绝对值。因此，稳妥做法是将所有概率 × 10⁶（或其他足够大因子）后四舍五入为 int，再丢弃小数部分。
- 直接用
double作freq成员，priority_queue比较可能因==判等失效，引发未定义行为 - 若原始数据已是整数频次（如字符计数），无需缩放；但需检查是否全为零，避免除零或空队列
- 归一化不是必须步骤——哈夫曼只依赖排序，不依赖和为 1
构建完成后的编码表看似简单，但真正容易被忽略的是：不同输入顺序下相同频次的字符，可能生成结构不同但同样最优的树，进而导致编码不唯一。这不是 bug，是算法固有性质；若需确定性输出（如用于校验），得在比较器中加入字符值的次级排序。
