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