参考：胡凡，曾磊「算法笔记」，emmmmm算是梳理吧。图片和部分描述均来自此书～
引：合并果子问题
n堆已知质量的果子，需要把他们合并为一堆，但每次只能合二为一，并消耗与这两堆果子总质量相同的体力。怎样使体力消耗最少？
-
分析
- 每次合二为一会使总堆数减1，因此总的合并次数一定是n-1。
- 每次都合并质量最少的两堆，让质量大的果子堆尽量少参与合并。
- 消耗体力之和即∑ (质量✖️合并次数)，在哈夫曼树中，所有原始的果堆都是叶结点，合并次数即叶结点到树根的路径长度。
- ∑ (质量✖️合并次数)即树的带权路径长度（Weighted Path Length）
哈夫曼树（最优二叉树）
已知n个数，寻找一棵树，使得所有叶子结点恰为这n个数，并且树的带权路径长度最小。
对于同一组叶子结点，哈夫曼树可能不唯一，但最小WPL唯一。
-
实现
利用小顶堆, 堆顶元素是当前堆的最小元素（c++ stl的priority_queue就可）。始终维护这个小顶堆。
- 用n个元素建堆
- 选择最小的两个元素a、b，从堆中删除，并将a+b插入到堆中。
- 重复2，直至堆中只剩一个元素。
-
补充： priority_queue用法
-
size(), empty()，查看/删除堆顶前注意判空
push(Elem e) 复杂度O(log n)
top() 查看堆顶
pop() 队首出队（删除堆顶元素） - 优先级设置：默认大顶堆 （优先级最高的是堆顶，参数是定义less的）。
声明一个小顶堆：priority_queue <int, vector<int>, greater<>> mq;
vector<>表示底层数据结构的容器。
-
size(), empty()，查看/删除堆顶前注意判空
-
结构体定义排序规则：2种都🉑️
模板题codeup 21142 合并果子
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
typedef long long LL;
using namespace std;
priority_queue<LL, vector<LL>, greater<>> mq;
// 有些版本编译器需要greater<int>
int main() {
int nn;
LL temp, wpl = 0;
scanf("%d", &nn);
for (int i = 0; i < nn; ++i) {
scanf("%lld", &temp);
mq.push(temp);
}
while (mq.size() > 1) {
LL a = mq.top();
mq.pop();
LL b = mq.top();
wpl += (a + b);
mq.pop();
mq.push(a + b);
}
printf("%lld\n", wpl);
return 0;
}
哈夫曼编码
-
前缀编码
对任意一棵二叉树，若将树中所有分支都编码，比如左表示0，右表示1。那么任何一个结点的编号（根到当前结点路径上的数连起来）都是树中唯一的。而且，任何非叶结点的编号一定是某（些）结点编号的前缀；任何叶结点的编号一定不是任何结点编号的前缀。- 二叉树可以用来实现前缀编码
- 前缀编码意义在于解码不混淆（非前缀编码举例：0—A，1—B，01—C，则01到底是什么呢）
-
哈夫曼编码是能使给定字符串编码为01串后，长度最短的前缀编码
- 哈夫曼编码是针对确定的字符串而言的。确定的字符串才能知道各字符的出现次数（权重），以此为据构建哈夫曼树。
