因std::priority_queue默认大顶堆，须用lambda按freq升序（a->freq > b->freq）构造小顶堆；否则top()返回高频节点致WPL非最优，且裸指针不可用std::greater，还需防空堆崩溃。
为什么直接用 std::priority_queue 实现哈夫曼树构建时，自定义比较要小心？
因为哈夫曼算法依赖「频率最小的两个节点优先合并」，而 std::priority_queue 默认是大顶堆，必须显式翻转逻辑。若只写 greater 会出错——指针比较毫无意义，必须传入自定义仿函数或 lambda，按 freq 值升序排列。
常见错误现象：top() 返回高频节点，导致编码长度变长、总加权路径长（WPL）非最优。
- 正确做法：用 lambda 捕获成员访问，例如
[](const Node* a, const Node* b) { return a->freq > b->freq; }（注意是>实现小顶堆） - 不能直接用
std::greater，C++ 不支持对裸指针自动解引用比较 - 若节点存值而非指针（如
Node对象），需重载operator 且语义为「频率小者优先级高」
构建哈夫曼树后，如何安全生成每个字符的二进制编码？
不能从根向下 DFS 硬编码左右为 0/1，因为树结构由贪心合并动态生成，左右子树无业务含义；必须从叶子反向回溯到根，边走边拼接，最后反转字符串。
使用场景：字符集不固定（如文件频次统计后建树），需支持任意 char 或 int 键。
- 给每个
Node加char ch和bool is_leaf字段，仅叶子存有效字符 - 建树完成后，遍历所有叶子节点，调用递归函数
get_code(Node* leaf, string& code)，每次进入左子树 push_back('0')，右子树 push_back('1') - 务必在递归返回前
code.pop_back()回溯，否则后续叶子编码串污染 - 最终得到的编码是逆序的，需调用
reverse(code.begin(), code.end())
贪心选择性质在哈夫曼算法中哪一步被实际验证？
不是「选最小两个就一定对」，而是「存在一棵最优前缀码树，其两个最小频率字符作为兄弟叶节点」——这个结构性结论支撑了每轮合并的合法性。代码里体现为：只要当前队列 size ≥ 2，就无条件取 top 两次，合并后推回，不回溯、不剪枝。
性能影响：时间复杂度 O(n log n)，其中 n 是不同字符数；若字符集极大（如 Unicode），需先哈希统计频次，避免 vector 遍历开销。
- 合并新节点的
freq必须设为两子节点freq之和，不可用计数器累加 - 不要在合并时立即生成编码字符串，延迟到树建完再批量提取，避免重复字符串拷贝
- 若输入频次含 0（如某字符未出现），应预过滤，否则会导致空节点参与合并、破坏树结构
完整可运行的核心源码片段（不含 I/O，专注算法主干）
struct Node {
char ch;
int freq;
Node *left, *right;
bool is_leaf;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr), is_leaf(true) {}
Node(Node* l, Node* r) : ch(0), freq(l->freq + r->freq), left(l), right(r), is_leaf(false) {}
};
<p>string get_code(Node<em> root, Node</em> target) {
if (!root) return "";
if (root == target && root->is_leaf) return "";
string left = get_code(root->left, target);
if (!left.empty()) return "0" + left;
string right = get_code(root->right, target);
if (!right.empty()) return "1" + right;
return "";
}</p><p>// 主构建逻辑
Node<em> build_huffman(const vector<pair int>>& freqs) {
priority_queue<node>, vector<node>>, function<bool>, Node<em>)>> pq(
[](Node</em> a, Node* b) { return a->freq > b->freq; }
);
for (auto [c, f] : freqs) pq.push(new Node(c, f));</bool></node></node></pair></em></p><pre class="brush:php;toolbar:false;">while (pq.size() > 1) {
Node* a = pq.top(); pq.pop();
Node* b = pq.top(); pq.pop();
pq.push(new Node(a, b));
}
return pq.top();
}
注意：真实项目中需配套 delete_tree() 释放内存；若用智能指针，priority_queue 的比较逻辑要适配 shared_ptr 解引用。最易忽略的是——合并过程中未检查 pq.empty() 就调用 top()，一旦输入为空或单字符，直接崩溃。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
