哈夫曼树构建采用贪心策略，每次合并权值最小的两子树，通过优先队列或手写堆实现最小堆，结合频次统计与编码表生成，确保WPL最小且编码为前缀码。
一、构建哈夫曼树的贪心策略原理
哈夫曼编码通过构造带权路径长度最小的二叉树实现最优前缀码，其核心在于每次合并权值最小的两个子树，该操作具备贪心选择性质：局部最优（当前最小两节点合并）可导出全局最优（WPL最小）。算法依赖优先队列维护节点权值，确保每次取最小操作的时间复杂度可控。
1、定义节点结构体，包含字符、权值、左右子节点指针；
2、将所有叶子节点（字符及其频次）插入最小堆（priority_queue）；
3、当堆中节点数大于1时，连续弹出两个权值最小的节点；
立即学习“C++免费学习笔记（深入）”；
4、创建新内部节点，权值为二者之和，左指针指向第一个弹出节点，右指针指向第二个；
5、将新节点重新压入堆中；
6、重复步骤3至5，直至堆中仅剩一个节点，即为哈夫曼树根节点。
二、使用std::priority_queue实现最小堆
C++标准库未提供直接的最小堆容器，但可通过自定义比较器使priority_queue实现最小堆行为，避免手动实现堆逻辑，提升代码简洁性与可靠性。
1、声明priority_queue类型：priority_queue
2、定义Compare仿函数，重载operator()，返回left->weight > right->weight；
3、所有叶子节点指针依次push进minHeap；
4、在循环中调用minHeap.top()获取最小节点，minHeap.pop()移除；
5、构造父节点后，调用minHeap.push(newNode)插入；
6、循环终止条件为minHeap.size() == 1。
三、手写最小堆数组实现以完全控制下标逻辑
当需规避STL分配开销或教学演示底层堆结构时，可采用数组模拟二叉堆，通过父子节点下标关系（parent=i/2, left=2i, right=2i+1）维护最小堆性质，适用于嵌入式或性能敏感场景。
1、预分配足够大小的Node** heap数组，记录堆中节点指针；
2、实现heapify_down函数：从指定索引开始，比较当前节点与左右子节点权值，若当前权值大于任一子节点，则交换并递归下沉；
3、实现insert函数：将新节点置于末尾，执行heapify_up上浮调整；
4、实现extract_min函数：取heap[0]，用末尾节点覆盖heap[0]，size减1，再heapify_down(0)；
5、初始化阶段将各叶子节点调用insert；
6、主循环中连续两次调用extract_min获取最小两节点。
四、字符频次统计与输入预处理分离设计
将频次统计逻辑与哈夫曼树构建解耦，可支持多种输入源（如字符串字面量、文件流、map映射），增强算法复用性，避免硬编码频次数据导致的耦合问题。
1、接收const string& input参数，遍历统计每个char出现次数，存入unordered_map
2、过滤掉频次为0的字符，确保每个叶子节点权值为正整数；
3、对freq中每对键值，new Node(c, count)，加入候选节点集合；
4、若输入为空，直接返回空指针；
5、若仅有一个唯一字符，手动构造单节点树（左/右设为nullptr，权值为频次）；
6、将候选节点集合传入树构建函数，不依赖具体输入形式。
五、编码表生成与递归遍历路径记录
哈夫曼树构建完成后，需从根节点深度优先遍历至每个叶子，沿左分支记'0'、右分支记'1'，拼接路径字符串形成对应字符的二进制编码，该过程必须严格区分左右子树方向以保证前缀码性质。
1、定义void generateCodes(Node* root, string code, unordered_map
2、若root为nullptr，直接返回；
3、若root->left == nullptr 且 root->right == nullptr，则huffmanCode[root->ch] = code；
4、否则，递归调用generateCodes(root->left, code + "0", huffmanCode)；
5、递归调用generateCodes(root->right, code + "1", huffmanCode)；
6、初始调用传入根节点、空字符串""和空map，结束后huffmanCode即含全部字符编码映射。
