题解 | #【模板】哈夫曼编码#

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
    long long val;
    node* left,*right;
    node(long long a) : val(a) {left=right=nullptr;}
};
using lnode = node*;
struct cmp {
    bool operator()(lnode& l, lnode& r) {
    return l->val > r->val;
    }
};

class huffman {
    node *root;
    priority_queue<node*,vector<node*>,cmp> que;
public:
    long long total=0;
    void init_que(vector<long long>& v) {
        for (auto i:v) {
            auto node_new = new node(i);
            que.push(node_new);
        }
        build_tree();
        total = calc_weight(root, 0);
    }
    void build_tree() {
        
        if (que.size()==1) {
            auto tmp = new node(0);
            que.push(tmp);
        }
        while (!que.empty()) {
            auto left = que.top();
            que.pop();
            auto right = que.top();
            que.pop();
            auto cur=new node(left->val+right->val);
            cur->left = left;
            cur->right = right;
            if (que.empty()) {
                root = cur;
                break;
            }
            que.push(cur);
        }
        
    }
    long long calc_weight(lnode cur, long long idx=0) {
        if (cur && cur->left==nullptr && cur->right==nullptr) {
            return idx*cur->val;
        }
        return calc_weight(cur->left,idx+1) + calc_weight(cur->right,idx+1);
    }
};

int main() {
    int n;
    cin >> n;
    vector<long long> v(n);
    for (auto &i:v) cin >> i;
    huffman tree;
    tree.init_que(v);
    cout << tree.total << endl;
}
// 64 位输出请用 printf("%lld")