【题解】哈夫曼编码

题意

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

题解

由于我们需要每次选择两个最小的数来构造哈夫曼树,每次进行排序肯定不行,这就需要用到小根堆,即优先队列。存入优先队列的是当前这棵哈夫曼树,并记录其根节点的权值。我们每次从优先队列中取出两个值,小的值作为左儿子,大的值作为右儿子,新树根的权值为左右儿子权值之和,并记录下子树大小,将先建的树入队,若两个节点的权值相同,子树大的作为右儿子,反之作为左儿子。这些记录值都可以在结构体或者类中实现。当队列中只有一个元素时,就说明哈夫曼树构造完成了。对于构造完的哈夫曼树,我们可以跑一个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;
}
全部评论

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
frutiger:逆天,我家就安阳的,这hr咋能说3k的,你送外卖不比这工资高得多?还说大厂来的6k,打发叫花子的呢?这hr是怎么做到说昧良心的话的
找工作时遇到的神仙HR
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务