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

知识点：

1.优先队列使用：优先队列cmp的格式

2.结构体一定要赋值：tree* left=NULL;，否则初始化为奇奇怪怪的随机数，容易出错。

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

long long sum=0;

//思路1：构造链表
typedef struct tree{
    long long val;
    tree* left=NULL;
    tree *right=NULL;
    tree *parent=NULL;
}tree;

// bool cmp(tree *a, tree *b){
//     if(a->val < b->val) 
//         return true;
//     else
//         return false;
// }

struct cmp{
    bool operator()(tree *a, tree *b) const{
        return a->val > b-> val;
    }
};

int getSum(tree* root,int deep){
    // cout<<" now:"<<root->val;
    // if(root->left){
    //     cout<<" left:"<<root->left->val;
    // }
    // else{
    //     cout<<" NULL";
    // }
    // if(root->right){
    //     cout<<" right:"<<root->right->val;
    // }
    // else{
    //     cout<<" NULL";
    // }
    // cout<<" deep:"<<deep;
    // cout<<endl;
    if(root->left==NULL && root->right==NULL){
        sum+=deep*root->val;
        return 0;
    }
    if(root->left){
        getSum(root->left,deep+1);
    }
    if(root->right){
        getSum(root->right,deep+1);
    }
    return 0;


}

int main(){
    int n;
    cin>>n;
    // vector<tree*> list(n);
    priority_queue<tree*,vector<tree*>,cmp> list;


    for(int i=0;i<n;i++){
        tree* t=new tree;
        cin>>t->val;
        list.push(t);
    }
    // sort(list.begin(),list.end(),cmp);
    while(1){
        // cout<<"list.size:"<<list.size()<<" ";
        // for(auto i=0;i<list.size();i++){
        //     cout<<list[i]->val<<" ";
        // }
        // cout<<endl;
        // cout<<list.top()->val<<" ";

        if(list.size()==1){
            break;
        }
        tree* now=new tree;
        tree* a=list.top();
        list.pop();

        // cout<<list.top()->val<<" ";
        // cout<<endl;

        tree *b=list.top();
        list.pop();
        // for(int i=0;i<list.size();i++){
        //     cout<<list[i]->val<<" ";
        // }
        // cout<<endl;

        now->val=a->val+b->val;
        now->left=a;
        now->right=b;
        list.push(now);
        // if(now->val==75){
        //     cout<<"-----------";
        // }
        // sort(list.begin(),list.end(),cmp);
    }
    getSum(list.top(),0);
    cout<<sum;
    //329 232  





}