树的带权路径长度（Weight Path Length of Tree, WPL)等于它所有叶子结点的带权路径长度之后
哈夫曼问题：已知n个数，寻找一棵树，使得树的所有叶子结点的权值恰好为着n个数，并且使得这棵树的带权路径长度最小。带权路径长度最小的树被称为哈夫曼树（又称最优二叉树）。显然，对同一组叶子结点来说，哈夫曼树可以是不唯一的，但是最小带权路径长度一定是唯一的
构造一棵哈夫曼树操作：
- 初始状态下共有n个结点（结点的权值分别是给定的n个数），将它们视作n棵只有一个结点的树。
- 合并其中根结点权值最小的两棵树，生成两棵树根结点的父结点，权值为这两个根结点的权值之和，这样树的数量就减少一个
- 重复操作2， 直到只剩下一棵树为止，这棵树就是哈夫曼树
哈夫曼树的构建思想，就是反复选择两个最小的元素，合并，直到只剩下一个元素。
合并果子问题(codeup 21142)可以直接使用优先队列来实现。
//输入
5
1 2 2 3 6
//输出
30
实现
#include<cstdio>
#include<queue>
using namespace std;
//代表小顶堆的优先队列
priority_queue<long long, vector<long long>, greater<long long>> q;
int main() {
int n;
long long temp, x, y, ans = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%lld", &temp);
q.push(temp); //将初始重量压入优先队列
}
while(q.size() > 1) { //只要优先队列中至少有两个元素
x = q.top();
q.pop();
y = q.top();
q.pop();
q.push(x + y); //取出堆顶的两个元素，求和后压入优先队列
ans += x + y; //累计求和的结果
}
printf("%lld\n", ans); //ans即为消耗的最小体力
return 0;
}
哈夫曼编码
哈夫曼编码是针对确定的字符串来讲的。只有对确定的字符串，才能根据其中各字符的出现次数建立哈夫曼树，于是有对应的哈夫曼编码。
其中前缀编码等等和哈夫曼编码实现在此不细说，其同哈夫曼树相似。
