哈夫曼树构建有五种方法：一是优先队列法，用最小堆每次取两个最小权值节点合并；二是数组模拟堆法，手动实现堆操作；三是map与set组合法，按权值分组管理节点；四是递归分治法，排序后递归划分频次数组；五是迭代双队列法，适用于已排序输入，时间复杂度o(n)。
一、构建哈夫曼树的优先队列法
哈夫曼树的构建依赖于贪心策略：每次选取权值最小的两个节点合并为新节点，重复该过程直至只剩一个根节点。优先队列（最小堆）可高效支持反复取最小、插入新节点操作，时间复杂度为O(n log n)。
1、定义节点结构体，包含字符、权值、左右子指针，并重载小于运算符以支持最小堆排序。
2、遍历字符频次映射表，为每个字符创建叶子节点，并将所有节点压入priority_queue。
3、当队列中节点数大于1时，连续弹出两个最小权值节点，构造新内部节点，其权值为二者之和，左指针指向第一弹出节点，右指针指向第二弹出节点。
4、将新节点重新入队，继续循环直至队列仅剩一个节点，该节点即为哈夫曼树根节点。
二、基于数组模拟堆的手动建堆法
不使用STL容器时，可通过静态数组模拟最小堆结构，手动实现堆化、插入与删除逻辑，适用于嵌入式或受限环境，避免动态内存分配开销。
1、预分配大小为2n−1的Node数组，前n个位置存放初始叶子节点，按权值升序排列。
2、从最后一个非叶节点（索引为n/2−1）开始向上执行sift-down操作，构建初始最小堆。
3、设有效节点数为size，每次取堆顶（索引0）作为最小节点，将其与末尾节点交换，size减1，再对新堆顶执行sift-down恢复堆序。
4、重复取两次最小节点，合并后插入堆底位置，调用sift-up使其上浮至正确位置，直到堆中只剩一个节点。
三、使用map与set组合的有序集合法
利用std::map自动按键排序特性维护权值→节点指针映射，配合std::set管理相同权值的多个节点，确保合并时能稳定获取最小权值组中最先插入的两个节点。
1、声明map
2、获取weightMap.begin()所指的最小权值键值对，若其vector大小≥2，则从中取前两个节点；否则取该vector唯一节点，并从下一非空键值对中取首个节点。
3、合并两节点生成新节点，新权值为二者之和，将其插入weightMap[sum]的vector尾部。
4、若原vector长度为1，则清空该键对应vector并擦除该键；重复步骤2–3直至weightMap中仅剩一个键且其vector大小为1。
四、递归分治构造法（离线静态频次）
当所有字符频次已知且固定时，可将频次数组排序后递归划分，模拟最优合并顺序，无需显式建堆，适合教学演示或小规模数据。
1、将频次数组freq[]按升序排列，构造对应字符数组chars[]，保持一一对应关系。
2、定义递归函数buildHuffman(left, right)，当left == right时返回对应叶子节点；否则计算分割点mid，使左子区间权值和尽可能接近右子区间权值和。
3、以mid为界拆分数组，递归构建左子树buildHuffman(left, mid)和右子树buildHuffman(mid+1, right)。
4、创建父节点，左子指针指向左子树根，右子指针指向右子树根，权值为左右子树权值之和。
五、迭代双队列法（线性时间优化）
当输入频次已排序时，可利用两个队列分别存储原始叶子节点与合并生成的内部节点，每次从两队列队首取最小者，实现O(n)时间复杂度构建。
1、将已排序的频次数组转换为Node节点链表，存入queue
2、循环执行以下操作，直到leaves与merged中节点总数为1：比较leaves与merged的队首节点权值，取出较小者作为node1；再次比较并取出node2。
3、创建新节点，权值为node1->weight + node2->weight，node1作为左孩子，node2作为右孩子。
4、将新节点推入merged队尾，继续下一轮迭代。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
