含重复项的Huffman Coding树快速合并方法实现问询

核心思路 #

常规Huffman树构建用优先队列每次取两个最小节点合并，当存在大量相同频率的重复节点时，这种逐个合并的方式效率极低——比如10^{5个频率为1的节点，要做5*10}4次合并操作。

批量合并的本质是：对k个频率为f的节点，一次合并可生成⌊k/2⌋个频率为2f的节点，剩余k%2个频率为f的节点。如果有不同频率的批量节点，依然遵循Huffman“每次合并最小的两组”规则，但用批量计算替代单个节点操作，将时间复杂度从O(n logn)降到O(m logm)（m是不同频率的种类数，远小于重复节点的总数n）。

实现步骤 #

1. 统计频率频次：把所有重复的频率按「频率值，出现次数」分组，比如10^5个频率1的节点，就存为(1, 100000)。
2. 小顶堆维护：用小顶堆（优先队列）存储这些分组，保证每次能取出频率最小的分组。
3. 批量合并循环：每次取出堆顶的1~2组（取决于堆中元素数量），计算合并后的新分组，放回堆中，直到堆中只剩一个分组（即Huffman树的根节点）。

C++代码实现 #

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 小顶堆：按频率升序排列，pair<频率值, 对应节点数量>
using HuffmanGroup = pair<long long, long long>;
priority_queue<HuffmanGroup, vector<HuffmanGroup>, greater<HuffmanGroup>> min_heap;

// 计算Huffman编码的总代价（可扩展为构建树结构）
long long batchHuffman(const unordered_map<long long, long long>& freq_count) {
    // 初始化堆：将所有频率分组入堆
    for (const auto& [freq, cnt] : freq_count) {
        min_heap.emplace(freq, cnt);
    }

    long long total_cost = 0;

    while (min_heap.size() > 1) {
        // 取出第一个最小频率分组
        auto [f1, c1] = min_heap.top();
        min_heap.pop();

        // 取出第二个最小频率分组
        auto [f2, c2] = min_heap.top();
        min_heap.pop();

        if (f1 == f2) {
            // 相同频率分组：批量合并所有可合并的节点
            long long total_nodes = c1 + c2;
            long long new_freq = f1 * 2;
            long long new_cnt = total_nodes / 2;
            total_cost += new_freq * new_cnt; // 累加新生成节点的总代价

            // 剩余未合并的单个节点放回堆中
            if (total_nodes % 2 != 0) {
                min_heap.emplace(f1, 1);
            }
            // 新生成的分组入堆
            if (new_cnt > 0) {
                min_heap.emplace(new_freq, new_cnt);
            }
        } else {
            // 不同频率分组：只能取数量少的那组进行一一合并
            long long merge_cnt = min(c1, c2);
            long long new_freq = f1 + f2;
            total_cost += new_freq * merge_cnt;

            // 剩余未合并的节点放回堆中
            if (c1 > merge_cnt) {
                min_heap.emplace(f1, c1 - merge_cnt);
            }
            if (c2 > merge_cnt) {
                min_heap.emplace(f2, c2 - merge_cnt);
            }
            // 新生成的分组入堆
            min_heap.emplace(new_freq, merge_cnt);
        }
    }

    return total_cost;
}

int main() {
    // 测试用例：100000个频率为1的节点
    unordered_map<long long, long long> freq_count;
    freq_count[1] = 100000;

    long long cost = batchHuffman(freq_count);
    cout << "Huffman总代价：" << cost << endl;

    return 0;
}

代码解释 #

1. 数据结构选择：用unordered_map快速统计每个频率的出现次数；小顶堆priority_queue保证每次能获取当前最小频率的分组，符合Huffman的核心规则。
2. 相同频率合并优化：这是效率提升的关键——比如10^{5个频率1的节点，一次操作就能合并成5*10}4个频率2的节点，而非执行5*10^4次单个合并。
3. 不同频率合并逻辑：当两组频率不同时，只能按数量少的那组进行一一合并，生成频率为两者之和的新节点，剩余节点放回堆中继续参与后续合并。
4. 总代价计算：Huffman编码的总代价等于所有非叶子节点的频率之和，代码中每次合并时累加新生成节点的频率乘以数量，最终得到总代价。

扩展说明 #

如果需要实际构建Huffman树的结构，可以将pair替换为自定义结构体，添加子节点指针、节点类型（叶子/非叶子）等字段，在批量合并时记录节点间的父子关系。但对于大规模重复节点的场景，上述代码已经能满足核心的效率优化需求。

内容的提问来源于stack exchange，提问作者Phere Salad