网站建设 知乎,seo网络推广,wordpress的登录地址,漳州做网站建设目录
Huffman树
定义
运用情况
注意事项
解题思路
AcWing 148. 合并果子
题目描述
运行代码
代码思路
其它代码
代码思路
Huffman树
定义
它是一种最优二叉树。通过构建带权路径长度最小的二叉树#xff0c;经常用于数据压缩等领域。
运用情况
在数据压缩中经常用于数据压缩等领域。
运用情况
在数据压缩中如赫夫曼编码可实现高效的无损数据压缩。在信息传输中减少传输的数据量。
注意事项
权值的确定要合理。构建过程要准确确保得到最优树结构。
解题思路
首先根据给定的权值构建初始森林。不断选取权值最小的两个节点合并成一个新节点新节点的权值为两节点权值之和。重复这个过程直到只剩下一个节点该节点就是 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_queueint, vectorint, greaterint 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 中这就是合并这两堆果子所消耗的体力然后将合并后的新数量 ab 再压入堆中。这样不断进行合并操作直到堆中最后只剩下一个元素此时 total 中存储的就是最小体力耗费值。最后将其输出。
其它代码
#include iostream
#include queue
using namespace std;
int main()
{int n; cin n;priority_queueint, vectorint, greaterint 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 中这就是合并这两堆果子消耗的体力然后将合并后的新值 ab 再压入堆中这样不断地合并堆中的元素直到最后堆中只剩下一个元素。最后输出计算得到的最小体力耗费值 res。
