哈夫曼

​ 说起哈夫曼树及其思想，最经典也是最早接触的当属合并果子了。哈夫曼反映的经典贪心思想与其数学逻辑在初学者中独占一席，虽然其思想简单易懂，但其代码实现起来并不简单易懂，网上的代码大多都是用指针、内定义函数、地址符等来实现的，像我这种蒟蒻总是容易看得一头雾水，十分的不友好，考虑到哈夫曼树通常是静态的，所以我就敲出来了稍微易于理解一点的静态实现代码。

以下以哈夫曼编码为例

题目链接

上代码：

#include <bits/stdc++.h>
using namespace std;
int n,cnt;
struct haf{//哈夫曼树的每个节点
    int f;//指向父亲
    int num;//权值
    int xh;//序号（在tr数组中的下标）
    int l,r;//左右孩子
    string ans;//用于存储哈夫曼编码
    inline bool operator < (const haf &b)const{//重载运算符，以便使用优先队列
        if(num!=b.num)return num>=b.num;
        return ch>b.ch;
    }
}tr[10005];
void dfs(int p,string now){//深搜遍历得出编码，p为当前节点，now为以记录了的编码
    if(tr[p].l==-1&&tr[p].r==-1){
        tr[p].ans=now;
        return ;
    }
    dfs(tr[p].l,now+"0");
    dfs(tr[p].r,now+"1");
}
int main() {
    while(cin>>n){
        priority_queue <haf> q;
        cnt=n;
        for(int i=1;i<=n;i++){
            cin>>tr[i].ch>>tr[i].num;
            tr[i].xh=i;
            tr[i].l=tr[i].r=tr[i].f=-1;//f,l,r,全部初始化为-1
            q.push(tr[i]);
        }
        for(int i=1;i<n;i++){
            haf x=q.top();
            q.pop();
            haf y=q.top();
            q.pop();//这里满足：y.num>x.num
            tr[++cnt].num=x.num+y.num;
            tr[cnt].xh=cnt;
            if(x.num==y.num&&x.ch>y.ch)swap(x,y);//题目要求：x.ch<=y.ch
            tr[cnt].r=y.xh;
            tr[cnt].l=x.xh;
            tr[cnt].ch=y.ch;
            tr[y.xh].f=cnt;
            tr[x.xh].f=cnt;
            tr[cnt].f=-1;
            q.push(tr[cnt]);//q里的元素为从大到小
            /*
            q2=q;
            while(q2.size()){
                cout<<q2.top().num<<' ';
                q2.pop();
            }
            cout<<endl;
            */
            //上面的代码是可视化模拟哈夫曼合并过程功能的代码段
        }
        /*
        for(int i=1;i<=cnt;i++)cout<<"序号："<<i<<" ch:"<<tr[i].ch<<" num:"<<tr[i].num<<" l:"<<tr[i].l<<" r:"<<tr[i].r<<" f:"<<tr[i].f<<endl;
        */
        //上面一段是检查哈夫曼树各个节点的情况的功能的代码段
        dfs(cnt,""); 
        for(int i=1;i<=n;i++){
            if(i!=1)cout<<endl;
            cout<<tr[i].ch<<":"<<tr[i].ans;
        }
        cout<<endl;
    }
    return 0;
}

补充：

​ 静态化的哈夫曼这里用到了优先队列来选择权值最小的两个结点，优点是代码短，但要重载运算符，还要去学priority_queue。还有种方法是用小根堆，优点是复杂度比优先队列忧、不需要拓展其它知识（除非你没学过堆），但这样的话代码又要多一倍，而且实现起来十分麻烦。

​ 代码中的dfs函数（也就是求哈夫曼编码的函数）使用了自顶向下的方法遍历，得到编码的遍历方法也可以是自底向上，两种方法各有优劣（想想具体是哪些优劣？），根据实际情况而定。