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。