Huffman树——AcWing 148. 合并果子
目录
Huffman树
定义
运用情况
注意事项
解题思路
AcWing 148. 合并果子
题目描述
运行代码
代码思路
其它代码
代码思路
Huffman树
定义
它是一种最优二叉树。通过构建带权路径长度最小的二叉树，经常用于数据压缩等领域。
运用情况
- 在数据压缩中，如赫夫曼编码，可实现高效的无损数据压缩。
- 在信息传输中，减少传输的数据量。
注意事项
- 权值的确定要合理。
- 构建过程要准确，确保得到最优树结构。
解题思路
- 首先根据给定的权值构建初始森林。
- 不断选取权值最小的两个节点合并成一个新节点，新节点的权值为两节点权值之和。
- 重复这个过程直到只剩下一个节点，该节点就是 Huffman 树的根节点。
例如，假设有字符 A、B、C、D，权值分别为 5、7、2、8，构建 Huffman 树的过程如下：先选取权值 2 和 5 的节点 C 和 A 合并，得到新节点权值 7，此时森林中有节点 B（权值 7）、新节点（权值 7）和 D（权值 8），再选取两个权值 7 的节点合并，最后和 D 合并得到最终的 Huffman 树。通过这样的树结构可以生成相应的编码来实现数据压缩等目的。
AcWing 148. 合并果子
题目描述
AcWing 148. 合并果子 - AcWing
运行代码
#include <iostream>
#include <queue>
using namespace std;
int main() {int n;cin >> n;priority_queue<int, vector<int>, greater<int>> pq;for (int i = 0; i < n; i++) {int num;cin >> num;pq.push(num);}int total = 0;while (pq.size() > 1) {int a = pq.top();pq.pop();int b = pq.top();pq.pop();total += a + b;pq.push(a + b);}cout << total << endl;return 0;
}代码思路
- 首先，定义了变量
n用于接收果子的种类数。 - 创建了一个小顶堆（优先队列）
pq，用于存储各种果子的数量。 - 通过循环输入每种果子的数量并将其压入堆中。
- 然后，在一个循环中，只要堆中元素数量大于 1，就不断取出堆顶的两个最小元素
a和b，将它们的和累加到total中，这就是合并这两堆果子所消耗的体力，然后将合并后的新数量a+b再压入堆中。这样不断进行合并操作，直到堆中最后只剩下一个元素，此时total中存储的就是最小体力耗费值。最后将其输出。
其它代码
#include <iostream>
#include <queue>
using namespace std;
int main()
{int n; cin >> n;priority_queue<int, vector<int>, greater<int>> heap;while(n--){int x; cin >> x;heap.push(x);}int res = 0;while(heap.size() > 1){int a = heap.top();heap.pop();int b = heap.top();heap.pop();res += a + b;heap.push(a + b);}cout << res << endl;return 0;
}代码思路
- 首先定义了变量
n用于接收果子的种类数。 - 创建了一个小顶堆（优先队列）
heap。 - 通过一个循环读取每种果子的数量并将其压入堆中。
- 然后定义了结果变量
res并初始化为 0。 - 接着进入一个循环，只要堆中元素数量大于 1，就执行以下操作：从堆顶取出两个元素
a和b（这两个是当前堆中最小的两个元素），将它们的和累加到res中（这就是合并这两堆果子消耗的体力），然后将合并后的新值a+b再压入堆中，这样不断地合并堆中的元素，直到最后堆中只剩下一个元素。 - 最后输出计算得到的最小体力耗费值
res。