哈夫曼树的核心思想

哈夫曼树是一种贪心算法的应用。它利用权值较小的节点优先组合的原则，逐步构造一棵总带权路径长度最小的二叉树。

带权路径长度的计算：一棵树的带权路径长度是树中每个叶子节点的权值乘以其从根节点到该节点的路径长度，然后将所有叶子节点的带权路径长度相加。

构造哈夫曼树的关键问题

为什么贪心法有效？
- 在构造哈夫曼树的过程中，每次选择权值最小的两个节点合并，这样合并后新增的路径长度对整体带权路径长度的增加最小。
- 合并权值最小的两个节点可以保证最终结果是最优解。
为什么哈夫曼树是最优的？
- 哈夫曼树通过不断选择权值最小的两个节点来合并，保证最小权重节点的路径长度尽可能小。
- 通过数学归纳和证明（基于交换法则），可以证明哈夫曼树是最优二叉树。

详细的构造过程

输入数据

假设我们需要为以下权值集合构造哈夫曼树：

w = [5, 7, 10, 15, 20, 45]

步骤 1：初始化森林

每个权值（权重）视为一棵只有一个节点的单独树，并将这些树组成一个“森林”。每个节点权值对应一个叶子节点。

初始森林为：

{5, 7, 10, 15, 20, 45}

步骤 2：构造优先队列（最小堆）

为了快速找到森林中权值最小的两个树，通常使用最小堆（优先队列）来存储这些树。
堆排序能快速找到权值最小的两棵树，其时间复杂度为 O(log n) 。

初始化最小堆：

[5, 7, 10, 15, 20, 45]

步骤 3：重复以下操作，直至森林只剩下一棵树

操作核心：选最小的两棵树合并，生成一棵新树

第一次合并：
- 选择最小的两个节点： 5 和 7 。
- 构造一棵新树，新节点的权值为 5+7=12 。
- 新树的结构为：

         12
        /  \
       5    7

将这棵新树插入森林，同时删除 5 和 7 。更新森林：

   [10, 12, 15, 20, 45]

第二次合并：
- 选择最小的两个节点： 10 和 12 。
- 构造一棵新树，新节点的权值为 10+12=22 。
- 新树的结构为：

更新森林：

   [15, 20, 22, 45]

第三次合并：
- 选择最小的两个节点： 15 和 20 。
- 构造一棵新树，新节点的权值为 15+20=35 。
- 新树的结构为：

         35
        /  \
      15    20

更新森林：

   [22, 35, 45]

第四次合并：
- 选择最小的两个节点： 22 和 35 。
- 构造一棵新树，新节点的权值为 22+35=57 。
- 新树的结构为：

         57
        /  \
      22    35
     /  \   /  \
   10   12 15  20
       /  \
      5    7

更新森林：

   [45, 57]

第五次合并：
- 选择最小的两个节点： 45 和 57 。
- 构造最终的哈夫曼树，新节点的权值为 45+57=102 。
- 最终树的结构为：

               102
             /    \
           45      57
                 /    \
               22      35
             /  \    /   \
           10   12  15   20
               /  \
              5    7