【题解】哈夫曼编码

题意

给定一个长度为的数列，用这个数列构造一棵哈夫曼树，从根节点遍历到某个节点上边权的路径值即为该节点的哈夫曼编码，现在输出某些数组元素所对应的哈夫曼编码。

题解

由于我们需要每次选择两个最小的数来构造哈夫曼树，每次进行排序肯定不行，这就需要用到小根堆，即优先队列。存入优先队列的是当前这棵哈夫曼树，并记录其根节点的权值。我们每次从优先队列中取出两个值，小的值作为左儿子，大的值作为右儿子，新树根的权值为左右儿子权值之和，并记录下子树大小，将先建的树入队，若两个节点的权值相同，子树大的作为右儿子，反之作为左儿子。这些记录值都可以在结构体或者类中实现。当队列中只有一个元素时，就说明哈夫曼树构造完成了。对于构造完的哈夫曼树，我们可以跑一个dfs来获取每个节点的哈夫曼编码，可以预处理将每个节点的哈夫曼编码存在字典中，也可以离线化查询，在dfs时输出。

复杂度

时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
struct HaffmanTree
{
    HaffmanTree *lchild;
    HaffmanTree *rchild;
    int v;
    int size;
};
struct cmp
{
    bool operator()(HaffmanTree *&a,HaffmanTree *&b)const
    {
        return a->v>b->v;
    }
};
priority_queue<HaffmanTree*,vector<HaffmanTree*>,cmp>q;
map<int,string>vis;
void dfs(HaffmanTree *T,string str)
{
    if(T->lchild==NULL&&T->rchild==NULL)
    {
        vis[T->v]=str;
        return;
    }
    dfs(T->lchild,str+'0');
    dfs(T->rchild,str+'1');
}
int main()
{
    int n,Q;
    scanf("%d%d",&n,&Q);
    for(int i=0; i<n; i++)
    {
        int v;
        scanf("%d",&v);
        HaffmanTree *T=new HaffmanTree;
        T->lchild=NULL;
        T->rchild=NULL;
        T->v=v;
        T->size=0;
        q.push(T);
    }
    HaffmanTree *T;
    while(!q.empty())
    {
        HaffmanTree *T1=q.top();
        q.pop();
        if(q.empty())
        {
            T=T1;
            break;
        }
        HaffmanTree *T2=q.top();
        q.pop();
        T=new HaffmanTree;
        if(T1->v!=T2->v)
        {
            T->v=T1->v+T2->v;
            T->lchild=T1;
            T->rchild=T2;
            T->size=T1->size+T2->size+2;
            q.push(T);
        }
        else
        {
            T->v=T1->v+T2->v;
            if(T1->size>T2->size)
            {
                T->lchild=T2;
                T->rchild=T1;
            }
            else
            {
                T->lchild=T1;
                T->rchild=T2;
            }
            T->size=T1->size+T2->size+2;
            q.push(T);
        }
    }
    dfs(T,"");
    while(Q--)
    {
        int v;
        scanf("%d",&v);
        cout<<vis[v]<<endl;
    }
    return 0;
}