1、算法笔记贪心算法哈夫曼编码问题之欧阳文创编0023算法笔记【贪心算法】哈夫曼编码问题时间：2021.03.12创作：欧阳文1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率
2、低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（451+133+123+163+94+54）1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。 译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码
3、中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)。dT(c)也是字符c的前缀码长。则平均码长定义为：使平均码长达到最小的前缀码编码方案
4、称为C的最优前缀码。 2、构造哈弗曼编码 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下： (1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 (2)算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。 (3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 构造过程如图所示：
5、具体代码实现如下： (1)4d4.cpp，程序主文件cppview plaincopy1./4d4贪心算法哈夫曼算法2.#includestdafx.h3.#includeBinaryTree.h4.#includeMinHeap.h5.#include6.usingnamespacestd;7.constintN=6;8.templateclassHuffman;9.template10.BinaryTreeHuffmanTree(Typef,intn);11.template12.classHuffman13.14.friendBinaryTreeHuffmanTree(Type,int)
6、;15.public:16.operatorType()const17.18.returnweight;19.20./private:21.BinaryTreetree;22.Typeweight;23.;24.intmain()25.26.charc=0,a,b,c,d,e,f;27.intf=0,45,13,12,16,9,5;/下标从1开始28.BinaryTreet=HuffmanTree(f,N);29.cout各字符出现的对应频率分别为：endl;30.for(inti=1;i=N;i+)31.32.coutci:fi;33.34.coutendl;35.cout生成二叉树的前序遍
7、历结果为：endl;36.t.Pre_Order();37.coutendl;38.cout生成二叉树的中序遍历结果为：endl;39.t.In_Order();40.coutendl;41.t.DestroyTree();42.return0;43.44.template45.BinaryTreeHuffmanTree(Typef,intn)46.47./生成单节点树48.Huffman*w=newHuffmann+1;49.BinaryTreez,zero;50.for(inti=1;i=n;i+)51.52.z.MakeTree(i,zero,zero);53.wi.weight=fi;
8、54.wi.tree=z;55.56./建优先队列57.MinHeapHuffmanQ(n);58.for(inti=1;i=n;i+)Q.Insert(wi);59./反复合并最小频率树60.Huffmanx,y;61.for(inti=1;in;i+)62.63.x=Q.RemoveMin();64.y=Q.RemoveMin();65.z.MakeTree(0,x.tree,y.tree);66.x.weight+=y.weight;67.x.tree=z;68.Q.Insert(x);69.70.x=Q.RemoveMin();71.deletew;72.returnx.tree;73
9、. (2)BinaryTree.h 二叉树实现cppview plaincopy1.#include2.usingnamespacestd;3.template4.structBTNode5.6.Tdata;7.BTNode*lChild,*rChild;8.BTNode()9.10.lChild=rChild=NULL;11.12.BTNode(constT&val,BTNode*Childl=NULL,BTNode*Childr=NULL)13.14.data=val;15.lChild=Childl;16.rChild=Childr;17.18.BTNode*CopyTree()19.2
10、0.BTNode*nl,*nr,*nn;21.if(&data=NULL)22.returnNULL;23.nl=lChild-CopyTree();24.nr=rChild-CopyTree();25.nn=newBTNode(data,nl,nr);26.returnnn;27.28.;29.template30.classBinaryTree31.32.public:33.BTNode*root;34.BinaryTree();35.BinaryTree();36.voidPre_Order();37.voidIn_Order();38.voidPost_Order();39.intTr
11、eeHeight()const;40.intTreeNodeCount()const;41.voidDestroyTree();42.voidMakeTree(TpData,BinaryTreeleftTree,BinaryTreerightTree);43.voidChange(BTNode*r);44.private:45.voidDestroy(BTNode*&r);46.voidPreOrder(BTNode*r);47.voidInOrder(BTNode*r);48.voidPostOrder(BTNode*r);49.intHeight(constBTNode*r)const;5
12、0.intNodeCount(constBTNode*r)const;51.;52.template53.BinaryTree:BinaryTree()54.55.root=NULL;56.57.template58.BinaryTree:BinaryTree()59.60.61.template62.voidBinaryTree:Pre_Order()63.64.PreOrder(root);65.66.template67.voidBinaryTree:In_Order()68.69.InOrder(root);70.71.template72.voidBinaryTree:Post_Or
13、der()73.74.PostOrder(root);75.76.template77.intBinaryTree:TreeHeight()const78.79.returnHeight(root);80.81.template82.intBinaryTree:TreeNodeCount()const83.84.returnNodeCount(root);85.86.template87.voidBinaryTree:DestroyTree()88.89.Destroy(root);90.91.template92.voidBinaryTree:PreOrder(BTNode*r)93.94.
14、if(r!=NULL)95.96.coutdatalChild);98.PreOrder(r-rChild);99.100.101.template102.voidBinaryTree:InOrder(BTNode*r)103.104.if(r!=NULL)105.106.InOrder(r-lChild);107.coutdatarChild);109.110.111.template112.voidBinaryTree:PostOrder(BTNode*r)113.114.if(r!=NULL)115.116.PostOrder(r-lChild);117.PostOrder(r-rChi
15、ld);118.coutdata;119.120.121.template122.intBinaryTree:NodeCount(constBTNode*r)const123.124.if(r=NULL)125.return0;126.else127.return1+NodeCount(r-lChild)+NodeCount(r-rChild);128.129.template130.intBinaryTree:Height(constBTNode*r)const131.132.if(r=NULL)133.return0;134.else135.136.intlh,rh;137.lh=Heig
16、ht(r-lChild);138.rh=Height(r-rChild);139.return1+(lhrh?lh:rh);140.141.142.template143.voidBinaryTree:Destroy(BTNode*&r)144.145.if(r!=NULL)146.147.Destroy(r-lChild);148.Destroy(r-rChild);149.deleter;150.r=NULL;151.152.153.template154.voidBinaryTree:Change(BTNode*r)/将二叉树bt所有结点的左右子树交换155.156.BTNode*p;1
17、57.if(r)158.p=r-lChild;159.r-lChild=r-rChild;160.r-rChild=p;/左右子女交换161.Change(r-lChild);/交换左子树上所有结点的左右子树162.Change(r-rChild);/交换右子树上所有结点的左右子树163.164.165.template166.voidBinaryTree:MakeTree(TpData,BinaryTreeleftTree,BinaryTreerightTree)167.168.root=newBTNode();169.root-data=pData;170.root-lChild=left
18、Tree.root;171.root-rChild=rightTree.root;172. (3)MinHeap.h 最小堆实现cppview plaincopy1.#include2.usingnamespacestd;3.template4.classMinHeap5.6.private:7.T*heap;/元素数组，0号位置也储存元素8.intCurrentSize;/目前元素个数9.intMaxSize;/可容纳的最多元素个数10.voidFilterDown(constintstart,constintend);/自上往下调整，使关键字小的节点在上11.voidFilterUp(in
19、tstart);/自下往上调整12.public:13.MinHeap(intn=1000);14.MinHeap();15.boolInsert(constT&x);/插入元素16.TRemoveMin();/删除最小元素17.TGetMin();/取最小元素18.boolIsEmpty()const;19.boolIsFull()const;20.voidClear();21.;22.template23.MinHeap:MinHeap(intn)24.25.MaxSize=n;26.heap=newTMaxSize;27.CurrentSize=0;28.29.template30.Mi
20、nHeap:MinHeap()31.32.deleteheap;33.34.template35.voidMinHeap:FilterUp(intstart)/自下往上调整36.37.intj=start,i=(j-1)/2;/i指向j的双亲节点38.Ttemp=heapj;39.while(j0)40.41.if(heapi=temp)42.break;43.else44.45.heapj=heapi;46.j=i;47.i=(i-1)/2;48.49.50.heapj=temp;51.52.template53.voidMinHeap:FilterDown(constintstart,constintend)/自上往下调整，使关键字小的节点在上54.55.inti=start,j=2*i+1;56.Ttemp=heapi;57.while(j=end)58.59.if(jheapj+1)60.j+;61.if(temp=heapj)62.break;63.else64.65.heapi=heapj;66.i=j;67.j=2*j+1;68.69.70.heapi=temp;71.72.template73.boolMinHeap:Insert(constT&x)74.75.
