目录

牛客_AB32【模板】哈夫曼编码

题目解析

C++代码

Java代码

---

牛客_AB32【模板】哈夫曼编码

【模板】哈夫曼编码_牛客题霸_牛客网

描述：

        给出一个有n种字符组成的字符串，其中第ii种字符出现的次数为ai​。请你对该字符串应用哈夫曼编码，使得该字符串的长度尽可能短，求编码后的字符串的最短长度。

输入描述：

第一行输入一个整数nn (1≤n≤2⋅10^5)，表示字符种数。

第二行输入nn个整数aiai​ (1≤ai≤10^9)，表示每种字符的出现次数。

输出描述：

输出一行一个整数，表示编码后字符串的最短长度。

---

题目解析

         哈夫曼编码（Huffman Coding）是一种被广泛使用的可变长度编码方式，由David A. Huffman在1952年提出。它主要用于数据压缩领域，特别是当数据的某些部分比其他部分更频繁地出现时。哈夫曼编码基于一种贪心算法来构建一棵最优二叉树（通常称为哈夫曼树），用于对数据进行编码。

        以下是哈夫曼编码的基本概念和工作原理：

1. 频率统计：首先，统计输入数据中每个符号（如字符、单词或任何其他可识别的单元）出现的频率。

2. 构建哈夫曼树：使用这些频率作为权重，通过贪心算法构建一棵哈夫曼树。在构建过程中，权重最小的两个节点被合并为一个新的内部节点，该内部节点的权重为两个子节点权重之和。这个过程一直重复，直到只剩下一个节点（即树的根）。

3. 生成编码：在哈夫曼树中，从根节点到每个叶子节点的路径（通过左子节点或右子节点）被转换为一串二进制数，这就是该叶子节点对应符号的哈夫曼编码。由于树的构建是基于权重的，因此更常见的符号（即权重更大的符号）通常具有较短的编码，而不常见的符号则具有较长的编码。

4. 编码数据：使用生成的哈夫曼编码替换输入数据中的每个符号。

5. 解码数据：由于哈夫曼编码是前缀码（即任何符号的编码都不是另一个符号编码的前缀），因此解码过程相对简单。只需按照编码的二进制串在哈夫曼树中查找即可。

        哈夫曼编码是一种非常有效的数据压缩方法，特别适用于那些符号频率分布不均匀的数据。然而，由于需要构建哈夫曼树和生成编码，因此哈夫曼编码的压缩和解压过程相对较慢。此外，哈夫曼编码生成的压缩数据是自适应的，即不同的数据可能生成不同的哈夫曼树和编码，因此通常需要在压缩数据中附带哈夫曼树的信息以便于解压。

计算结果：

C++代码

#include <functional>
#include <iostream>
#include <queue>
using namespace std;
#define int long longsigned main()
{int n = 0, x = 0, ret = 0;cin >> n;priority_queue<int ,vector<int>, greater<int>> heap;while(n--){cin >> x;heap.push(x);}while(heap.size() != 1){long long x1 = heap.top();heap.pop();long long x2 = heap.top();heap.pop();heap.push(x1 + x2);ret += x1 + x2;}cout << ret << endl;return 0;
}

Java代码

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();PriorityQueue<Long> heap = new PriorityQueue<>();while(n-- != 0){long x = in.nextLong();heap.offer(x);}// 构建最优⼆叉树 / 构建哈夫曼树long ret = 0;while(heap.size() > 1){long t1 = heap.poll();long t2 = heap.poll();heap.offer(t1 + t2);ret += t1 + t2;}System.out.println(ret);} 
}