哈夫曼编码通过贪心策略构建最优二叉树：先用最小堆合并权值最小的两节点，再递归生成前缀码；可手动数组建堆优化性能，并用位操作压缩编码存储。
一、构建哈夫曼树的优先队列贪心策略
哈夫曼编码的核心在于利用贪心思想，每次合并权值最小的两个节点，以保证带权路径长度最小。该过程依赖最小堆（优先队列）动态维护当前所有待合并节点，确保每次都能在O(log n)时间内取出最小权值节点。
1、定义节点结构体，包含字符、权值、左右子指针；
2、将所有叶节点（字符及其频次）插入std::priority_queue，自定义比较器使队首为权值最小节点；
3、当队列中节点数大于1时，连续弹出两个最小权值节点，构造新父节点，权值为二者之和；
立即学习“C++免费学习笔记（深入）
”；
4、将新父节点重新压入队列；
5、重复步骤3–4直至队列仅剩一个节点，即为哈夫曼树根节点。
二、递归生成最优二进制编码字符串
从哈夫曼树根出发，向左子树走标记为'0'，向右子树走标记为'1'，递归遍历至所有叶节点，即可为每个字符生成唯一前缀码。该过程不依赖栈或迭代状态，天然避免歧义与重复。
1、编写递归函数，参数包括当前节点指针、当前编码字符串引用、存储字符-编码映射的unordered_map；
2、若当前节点为叶节点（左右子指针均为空），将字符与当前编码存入映射表；
3、若左子节点非空，将'0'追加至当前编码，递归访问左子树；
4、若右子节点非空，将'1'追加至当前编码，递归访问右子树；
5、递归返回前需对当前编码执行pop_back()回溯，确保路径字符串准确对应各分支。
三、使用数组模拟堆的手动建树实现
规避STL容器开销及内存分配不确定性，可采用静态数组+下标运算手动实现最小堆。适用于嵌入式环境或对缓存局部性敏感的场景，时间复杂度仍为O(n log n)，但常数因子更小。
1、预分配大小为2n−1的Node数组，前n个位置存放初始叶节点；
C函数速查手册（CHM版）
C函数速查手册（CHM版）
下载2、从最后一个非叶节点（下标为n/2−1）开始向上执行sift-down操作，构建初始最小堆；
3、设有效节点数为size，循环执行：取堆顶元素作为min1，sift-down后再次取堆顶为min2；
4、创建新节点，权值为min1.weight + min2.weight，左指针指向min1，右指针指向min2；
5、将新节点放入数组末尾，size加1，并对该位置执行sift-up操作以维持堆序。
四、位操作优化编码存储与输出
避免为每个字符单独保存std::string导致的冗余内存占用，可将编码序列压缩为uint64_t整数与位长元数据组合。尤其适合高频字符集（如ASCII）的紧凑表示与快速查表。
1、为每个字符分配一个uint64_t变量code_val与unsigned char code_len；
2、递归生成编码过程中，用位移与按位或操作逐位写入code_val，同步累加code_len；
3、输出时通过(code_val >> (64 − code_len)) & ((1ULL
4、对code_len为0的占位符节点跳过编码写入；
5、最终编码表以结构体数组形式组织，支持O(1)随机访问与O(k)比特级输出（k为码长）。
五、基于并查集逆向重构的无指针树表示法
消除动态指针带来的缓存不友好与内存碎片问题，改用并查集式父索引数组与子索引偏移量描述树结构。所有节点存储于连续内存块，便于SIMD批量处理与GPU迁移。
1、声明两个int数组：parent[2n−1]初始化为−1，child_offset[2n−1]初始化为0；
2、每次合并i与j节点时，新建节点k，设parent[i] = parent[j] = k，并更新child_offset[k]记录左右子位置；
3、叶节点索引范围为0到n−1，内部节点索引从n开始递增；
4、编码生成改为基于索引的栈式DFS：起始压入根索引，每次弹出后检查是否为叶节点（索引
5、栈中每个元素为pair
，分别表示当前节点索引与已生成编码值。