题解 | #哈夫曼树#

采用哈夫曼树的思想

在机试中最常考察优先队列的应用便是哈夫曼树(Huffman Tree)。在一颗树中，从任意一个结点到达另一个结点的通路被称为路径，该路径上所需经过的边的个数被称为该路径的长度。如果树中结点带有表示某种意义的权值，那么从根结点到达该结点的带权路径长度再乘以该结点的权值就被称为该结点的带权路径长度。树中所有叶子结点的带权路径长度之和为该树的带权路径长度之和。给定n个带有权值的结点，以它们为叶子结点构造一颗带权路径长度和最小的二叉树，该二叉树即为哈夫曼树，同时也称为最优树。

由于n个带有权值的结点构成的哈夫曼树可能不唯一，所以关于哈夫曼树的机试题往往考察的是求解最小带权路径长度和。哈夫曼树的求法：

1、将所有结点放入集合K

2、若集合K中的剩余结点数大于1，则取出权值最小的两个结点，将它们两个构造成某个新结点的左右子结点，设这个新结点的权值为其两个子结点的权值和，并将该新结点放入集合K。

3、若集合K中仅剩余一个结点，则该结点即为构造出的哈夫曼树的根结点。构造过程中，所有中间结点的权值和，即为该哈夫曼树的带权路径和。

#include <iostream>
#include <queue>

using namespace std;

int main() 
{
    int n;
    while (cin >> n) {
        priority_queue<int, vector<int>, greater<int>> pq;
        while (n--) {
            int val;
            cin >> val;
            pq.push(val);
        }
        int result = 0;
        while (pq.size() > 1) {
            int a = pq.top();
            pq.pop();
            int b = pq.top();
            pq.pop();
            pq.push(a+b);
            result += a + b;
        }
        cout << result << endl;
    }
    return 0;
}