<---大佬们点个赞吧qwq

$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $

题目描述

给定 $N$ 个权值作为 $N$ 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

现在，给定 $N$ 个叶子结点的信息，请你构造哈夫曼树，并输出该树的带权路径长度。

相关知识：
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 $1$，则从根结点到第 $L$ 层结点的路径长度为 $L-1$。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。

输入格式

第一行包含整数 $N$，表示叶子结点数量。

第二行包含 $N$ 个整数，表示每个叶子结点的权值。

输出格式

输出一个整数，表示生成哈夫曼树的带权路径长度。

数据范围

$2 \\le N \\le 1000$,
叶子结点的权值范围 $\[1,100\]$。

输入样例：

5
1 2 2 5 9

输出样例：

37

算法

(模拟) $O(n\log n)$

哈夫曼树生成的方法是这样的：
1. 挑两个权值最小的节点（直到节点数量少于 $2$ 个）
2. 往他们头上加一个权值为两者之和的父节点

因为每次挑的是两个权值最小的节点，所以这个算法显然是正确的。
由于我们只需要知道哈夫曼树的最短带权路径长度，所以我们可以不用模拟所有节点，只需要模拟最上一层的节点就行了。

由于只需要模拟最上一层的节点，所以我们可以用一个priority_queue来记录最上一层的节点的权值，每次取两个最小的，答案 += 两个节点权值之和（因为两个节点深度又多了 $1$），把一个权值为之前两个节点权值之和的节点加入priority_queue。

时间复杂度

因为用的是priority_queue，所以时间复杂度是 $O(n\log n)$。

空间复杂度

priority_queue的空间复杂度是 $O(n)$ 的。

C++ 代码

#include <iostream>
#include <queue> // 优先队列头文件

using namespace std;

int n;
priority_queue<int> q; // 模拟哈夫曼树

int main()
{
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        q.push(-x); // priority_queue默认是大根堆，如果我们想要把它变成小根堆的话，可以往里面添加原来数值的相反数
    }

    int res = 0; // res: 结果
    while (q.size() > 1) // 模拟哈夫曼树生成过程
    {
        // 挑两个最小的数
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();

        res -= a + b; // 把他们之和加到答案里（因为添加的时候是相反数，所以用 -=）
        q.push(a + b); // 合并节点
    }

    cout << res;

    return 0;
}

C++ 代码2

#include <iostream>
#include <queue> // 优先队列头文件

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>> q; // 大根堆 + 大于号 = 小根堆

int main()
{
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        q.push(x); // 加入节点
    }

    int res = 0; // res: 结果
    while (q.size() > 1) // 模拟哈夫曼树生成过程
    {
        // 挑两个最小的数
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();

        res += a + b; // 把他们之和加到答案里
        q.push(a + b); // 合并节点
    }

    cout << res;

    return 0;
}