引子 – 决策树

某操作有 A，B，C，D，E 这五种情况，代码如下：

if(operate == 'A')
  A情况的操作
else if(operate == 'B')
  B情况的操作
else if(operate == 'C')
  C情况的操作
else if(operate == 'D')
  D情况的操作
else
  E情况的操作

若该操作进行了10w次，A~E对应的频度为 5%，20%，30%，25%，20%

那么需要进行 10w * (5% * 1 + 20% *2 + 30% * 3 + 25% * 4 + 20% * 4) = 31.5w次判断

现在有个问题：如何更改决策的先后顺序使得 判断次数达到最小呢？ 高频优先

新增

• 哈夫曼树：通过构建二叉树合并权值最小的节点，常用于生成编码表。
• 代码优化：通过调整条件分支的顺序，直接减少高频操作的判断层级（如将 C放在第一层判断）。

代码优化并未严格采用哈夫曼树的结构，但借鉴了其 高频优先 的核心思想。

哈夫曼树及构造

在含有n个带权叶结点的二叉树中，其中带权路径长度WPL最小的二叉树称为哈夫曼树，也称为最优二叉树。

Q：给定N个权值（权值是每个节点上的数值）作为N个叶子结点，如何构造一棵哈夫曼树？

1）构造森林全是树 2）先用两小造新树 3）删除两小添新树 4）重复 2）3）直到根。

例：叶子结点 a，b，c，d的权值分别为 7，5，2，4，构造出一棵哈夫曼树（哈夫曼树不唯一）

阿Q备：

1、带权路径长度最短是在度相同的树中比较而得得结果，因此有最优二叉树，最优三叉树之称等等。

2、哈夫曼树构造过程不唯一，因此哈夫曼树不唯一，但是都是最优带权路径，（一般人为规定左支结点值< 右支结点值）。

题目

算法题

/*
题目描述
    一位老木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN（1 <= L1,L2,…,LN <=1000，且均为整数）个长度单位。
    我们认为切割时仅在整数点处切且没有木材损失。
    木匠发现，每一次切割花费的体力与该木棒的长度成正比，不妨设切割长度为1的木棒花费1单位体力。
    例如：若N = 3，L1 = 3,L2 = 4,L3 = 5，则木棒原长为12。
    木匠可以有多种切法，如：
    第一种切法先将12切成3+9.，花费12体力，再将9切成4+5，花费9体力，一共花费21体力；
    第二种切法还可以先将12切成4+8，花费12体力，再将8切成3+5，花费8体力，一共花费20体力。
    显然，后者比前者更省体力。
    那么，木匠至少要花费多少体力才能完成切割任务呢？

输入描述
    第1行：1个整数N(2<=N<=50000)
    第2 - N + 1行：每行1个整数Li(1<=Li<=1000)。

输出描述
    输出最小的体力消耗。

样例输入
    3
    3
    4
    5

样例输出
　　19
*/

// C++ STL容器 priority_queue<元素类型，该元素类型的数组，定义排序规则>；

priority_queue <int,vector<int>,greater<int> > q; // 从小到大的优先队列
q.push(1);      // 入队1，值在数组中自动遵循从小到大插入相应位置

q.top();  //只能在优先队列里使用，不能在普通队列里使用。如果是从小到大排列的，第一个肯定是最小的，最后一个是最大的。

q.size()      //返回q里元素个数

#include<iostream>
#include<queue>
#include<vector>


int main(){
    int strength, first_small, second_small;
    strength = 0;
    
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;

    // n个叶子结点
    int n;
    std::cin >> n;

    int val;
    // 构造森林全是树
    for(int i = 0; i < n; i++){
        std::cin >> val;
        q.push(val);
    }

    // 循环结束 - 只剩根
    while(q.size() > 1){
        // 先用两小造新树, 删除两小添新树
        first_small = q.top();
        q.pop();
        second_small = q.top();
        q.pop();

        strength += first_small + second_small;

        q.push(first_small + second_small);
    }
    // 哈夫曼树带权路径长度 - 最小消耗精力
    std::cout << strength;

    return 0;
}

阿Q：正难则反 – 有N个木棒，如何两两拼回去使得消耗的体力最小 -> 带权路径长度最小问题 -> 哈夫曼树

阿Q现在还没刷过算法题，首先想到的解法是：构造出整个哈夫曼树，然后去遍历哈夫曼树，累计叶子结点权值 * ( 叶子结点的高度 – 1）

但是看了这道题的算法解析后，AQ appaled !

C++ STL容器中有优先队列，入队元素可以根据定义的排序规则自动进行排序。借助优先队列（定义排序规则：从小到大），队头元素即为 结点权值最小的，出队俩队头元素相加即为 新树的权值，再将新树权值入队即可（先用两小造新树，删除两小添新树），一直到队内就一个元素为止。