题解 | #哈夫曼树#

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    priority_queue<int> priorityQueue;
    int num;
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        priorityQueue.push(-num); //取反变成小根堆
    }
    //哈夫曼树的权值,这里采用第一种
    // 1.等于 所有非叶子结点之和
    // 2.等于 每个叶子结点 * 所在的层数
    int sum = 0;
    while (priorityQueue.size() != 1) {
        int n1 = -priorityQueue.top();
        priorityQueue.pop();
        int n2 = -priorityQueue.top();
        priorityQueue.pop();
        int node = n1 + n2;
        sum += node;
        priorityQueue.push(-node); //取反加入堆里
    }
    printf("%d\n", sum);
}