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。