哈夫曼编码安全判断题解

问题本质

本题要求判断一个字符串使用哈夫曼编码（Huffman Coding）后的最小总存储位数是否小于等于给定的安全值 m。这实际上是在考察哈夫曼编码的核心原理：通过构建最优二叉树使编码总长度最小化。

哈夫曼编码原理深度剖析

1. 哈夫曼编码的核心思想

  • 给出现频率高的字符分配短编码
  • 给出现频率低的字符分配长编码
  • 保证没有一个编码是另一个编码的前缀（前缀码性质）
  • 通过这种策略，使整个字符串的编码总长度达到最小

2. 哈夫曼树的构建

哈夫曼树是一种带权路径长度最小的二叉树，构建过程如下：

  1. 将每个字符视为一个节点，权重为其出现频率
  2. 创建一个最小堆（优先队列），将所有节点放入
  3. 重复以下操作，直到堆中只剩一个节点（树的根）：
    • 从堆中取出两个权重最小的节点
    • 创建一个新节点，权重为这两个节点权重之和
    • 将这两个节点作为新节点的左右子节点
    • 将新节点放回堆中
  4. 剩下的最后一个节点就是哈夫曼树的根

代码实现

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    cin.ignore(); // 忽略第一行后的换行符，确保getline正常工作

    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line); // 读取整行，包含安全值和字符串
        
        if (line.empty()) {
            // 处理空行情况
            cout << "yes" << endl; // 空字符串总位数为0，通常安全
            continue;
        }
        
        // 使用字符串流解析该行
        stringstream ss(line);
        int m;
        string s;
        ss >> m;    // 读取安全值m
        ss >> s;    // 读取字符串，如果不存在则s为空
        
        long long total_bits = 0; // 使用long long防止大数溢出

        if (!s.empty()) { // 非空字符串才需要处理
            // 1. 统计字符频率
            map<char, int> freqMap;
            for (char c : s) {
                freqMap[c]++; // 计算每个字符出现的次数
            }
            
            // 2. 特殊情况：只有一种字符
            if (freqMap.size() == 1) {
                // 单一字符的哈夫曼编码：每个字符用1位
                total_bits = s.length();
            } 
            // 3. 一般情况：使用优先队列构建哈夫曼树
            else {
                // 创建小顶堆，存储字符频率
                priority_queue<long long, vector<long long>, greater<long long>> pq;
                
                // 将所有字符频率加入堆中
                for (auto& kv : freqMap) {
                    pq.push(kv.second);
                }
                
                // 4. 模拟哈夫曼树构建过程
                while (pq.size() > 1) { // 至少需要两个节点才能合并
                    // 取出两个频率最小的节点
                    long long a = pq.top(); pq.pop();
                    long long b = pq.top(); pq.pop();
                    
                    // 合并这两个节点
                    long long sum = a + b;
                    
                    // 累加合并代价（核心步骤！）
                    total_bits += sum;
                    
                    // 将新节点（合并结果）放回堆中
                    pq.push(sum);
                }
            }
        }
        // 空字符串时total_bits保持为0
        
        // 5. 比较结果并输出
        if (total_bits <= m) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }

    return 0;
}

代码详解

priority_queue<long long, vector<long long>, greater<long long>> pq;
  • 创建一个小顶堆（优先队***保每次取出的都是最小频率
  • greater<long long> 保证堆顶是最小元素
  • 使用long long防止大数溢出，因为合并代价可能非常大
for (auto& kv : freqMap) {
    pq.push(kv.second);
}
  • 将每个字符的频率值放入优先队列
  • 例如，对于"abcdd"，初始堆为[1, 1, 1, 2]
while (pq.size() > 1) {
    long long a = pq.top(); pq.pop();  // 1
    long long b = pq.top(); pq.pop();  // 2
    long long sum = a + b;             // 3
    total_bits += sum;                 // 4：关键步骤！
    pq.push(sum);                      // 5
}

  1. 取出频率最小的节点：long long a = pq.top(); pq.pop();

    • 从堆顶取出当前频率最小的节点
    • 例如，第一次迭代中，a = 1（假设是字符a）

  2. 取出频率次小的节点：long long b = pq.top(); pq.pop();

    • 从堆中取出当前频率第二小的节点
    • 例如，第一次迭代中，b = 1（假设是字符b）

  3. 合并两个节点：long long sum = a + b;

    • 创建新节点，频率为a+b
    • 这代表在哈夫曼树中，这两个节点有一个共同的父节点
    • 例如，sum = 1+1 = 2

  4. 累加合并代价：total_bits += sum;（最核心的步骤！）

    • 将合并代价（a+b）累加到总位数
    • 为什么正确：这次合并使所有在a和b子树中的字符编码长度都增加1位
    • 累加的sum = a+b 正好是这两个子树中所有字符在最终编码中额外增加的总位数
    • 例如，合并a(1)和b(1)后，a和b的编码长度都增加1，总增加位数 = 1+1 = 2

  5. 将新节点放回堆中：pq.push(sum);

    • 新节点将参与后续的合并
    • 例如，将新节点2放回堆中，堆变为[1, 2, 2]

特殊情况的深入分析

1. 空字符串

  • 没有字符需要编码
  • 总位数 = 0
  • 任何m ≥ 0，都应输出"yes"
  • 代码中通过if (!s.empty())处理，空字符串时total_bits保持为0

2. 单一字符（如"aaaaa"）

  • 关键问题：当只有一个字符时，哈夫曼算法无法进行合并（需要至少两个节点）
  • 编码规则：单一字符必须使用1位编码（不能为0位，否则无法区分）
  • 总位数 = 字符串长度 × 1 = 字符串长度
  • 例如："aaaaa"需要5位（如"00000"）
  • 代码中特殊处理：if (freqMap.size() == 1) total_bits = s.length();

3. 两种字符（如"aaab"）

  • 频率：a:3, b:1
  • 合并过程：
    • 取3和1，合并为4，总位数 += 4
    • 堆只剩一个节点，结束
  • 总位数 = 4
  • 验证：最优编码 a=0, b=1，总位数 = 3×1 + 1×1 = 4

4. 大数处理

  • 字符串长度最大可达10^6
  • 最坏情况（完全不平衡的哈夫曼树）：总位数可达O(n log n) ≈ 2×10^7
  • 使用long long（范围约9×10^18）确保不会溢出

算法复杂度分析

时间复杂度

  • 统计频率：O(L)，L为字符串长度
  • 构建优先队列：O(K)，K为不同字符数（小写字母，K≤26）
  • 哈夫曼树构建：O(K log K)，每次插入/删除操作O(log K)，共K-1次合并
  • 总时间复杂度：O(L + K log K) = O(L)，因为K≤26是常数

空间复杂度

  • 频率映射：O(K) = O(1)，因为小写字母最多26种
  • 优先队列：O(K) = O(1)
  • 总空间复杂度：O(1)，与输入大小无关