二叉树 | 哈夫曼树

参考：胡凡，曾磊「算法笔记」，emmmmm算是梳理吧。图片和部分描述均来自此书～

引：合并果子问题

n堆已知质量的果子，需要把他们合并为一堆，但每次只能合二为一，并消耗与这两堆果子总质量相同的体力。怎样使体力消耗最少？

• 分析

  • 每次合二为一会使总堆数减1，因此总的合并次数一定是n-1。
  • 每次都合并质量最少的两堆，让质量大的果子堆尽量少参与合并。
  • 消耗体力之和即∑ (质量✖️合并次数)，在哈夫曼树中，所有原始的果堆都是叶结点，合并次数即叶结点到树根的路径长度。
  • ∑ (质量✖️合并次数)即树的带权路径长度（Weighted Path Length）

哈夫曼树（最优二叉树）

已知n个数，寻找一棵树，使得所有叶子结点恰为这n个数，并且树的带权路径长度最小。

对于同一组叶子结点，哈夫曼树可能不唯一，但最小WPL唯一。

• 实现

  利用小顶堆, 堆顶元素是当前堆的最小元素（c++ stl的priority_queue就可）。始终维护这个小顶堆。

  1. 用n个元素建堆
  2. 选择最小的两个元素a、b，从堆中删除，并将a+b插入到堆中。
  3. 重复2，直至堆中只剩一个元素。

• 补充： priority_queue用法

  • size(), empty()，查看/删除堆顶前注意判空
    push(Elem e) 复杂度O(log n)
    top() 查看堆顶
    pop() 队首出队（删除堆顶元素）
  • 优先级设置：默认大顶堆 （优先级最高的是堆顶，参数是定义less的）。
    声明一个小顶堆：priority_queue <int, vector<int>, greater<>> mq;
    vector<>表示底层数据结构的容器。

• 结构体定义排序规则：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串后，长度最短的前缀编码

• 哈夫曼编码是针对确定的字符串而言的。确定的字符串才能知道各字符的出现次数（权重），以此为据构建哈夫曼树。