《算法笔记》9.8小节——图算法专题-＞哈夫曼树 问题 A: 算法6-12：自底向上的赫夫曼编码

题目描述

在通讯领域，经常需要将需要传送的文字转换成由二进制字符组成的字符串。在实际应用中，由于总是希望被传送的内容总长尽可能的短，如果对每个字符设计长度不等的编码，且让内容中出现次数较多的字符采用尽可能短的编码，则整个内容的总长便可以减少。另外，需要保证任何一个字符的编码都不是另一个字符的编码前缀，这种编码成为前缀编码。

而赫夫曼编码就是一种二进制前缀编码，其从叶子到根（自底向上）逆向求出每个字符的算法可以表示如下：

在本题中，读入n个字符所对应的权值，生成赫夫曼编码，并依次输出计算出的每一个赫夫曼编码。

输入

输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。

第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。

输出

共n行，每行一个字符串，表示对应字符的赫夫曼编码。

样例输入

8
5 29 7 8 14 23 3 11

样例输出

0110
10
1110
1111
110
00
0111
010

分析：题目可能限定了生成赫夫曼树的节点顺序，对于节点的排序是：先按照权值排序，权值相同时，按照出现的顺序排序，先出现的先用。在给出的select函数中，选定的最小两个权值，前一个权值的出现次序要在后一个之前，哪怕前一个权值大于后一个权值也是如此。

下面的代码直接用优先队列实现，没有使用给出的模板函数。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;

typedef struct node
{
    int val,index;
    struct node *lchild,*rchild,*father;
}node;

struct CompareNodePtr
{
    bool operator()(const node *a, const node *b)const
    {
        if(a->val==b->val)return a->index>b->index;  // val 相同，则 index 小的优先
        return a->val>b->val;  // val 小的优先
    }
};

void Free(node *root)
{
    if(root==NULL)return;
    Free(root->lchild);
    Free(root->rchild);
    free(root);
    return;
}

int main(void)
{
    #ifdef test
    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    clock_t start=clock();
    #endif //test

    int n;scanf("%d",&n);
    vector<node*>num(n+5);
    priority_queue<node*,vector<node*>,CompareNodePtr>q;

    for(int i=0;i<n;++i)
    {
        num[i]=(node*)malloc(sizeof(node));
        num[i]->lchild=num[i]->rchild=num[i]->father=NULL;
        num[i]->index=i+1;  // 赋值索引
        scanf("%d",&num[i]->val);
        q.push(num[i]);
    }

    int mergeIndex=n+1;
    node *x,*y;
    while(q.size()>1)
    {
        x=q.top(),q.pop();
        y=q.top(),q.pop();

        if(x->index>y->index)swap(x,y);//注意前一个的出现次序一定要小于后一个

        node *temp=(node*)malloc(sizeof(node));
        temp->val=x->val+y->val;
        temp->lchild=x,temp->rchild=y;
        x->father=y->father=temp;
        temp->index=mergeIndex++;  // 赋予新的索引值
        q.push(temp);
    }

    node *root=q.top();q.pop();

    for(int i=0;i<n;++i)
    {
        node *p=num[i];
        stack<int>sta;
        while(p!=root)
        {
            node *temp=p->father;
            if(p==temp->lchild)sta.push(0);
            else sta.push(1);
            p=temp;
        }
        while(!sta.empty())
        {
            printf("%d",sta.top());
            sta.pop();
        }
        printf("\n");
    }
    Free(root);

    #ifdef test
    clockid_t end=clock();
    double endtime=(double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\n\n\n\n");
    cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位
    cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
    #endif //test
    return 0;
}