0023算法笔记——【贪心算法】哈夫曼编码问题1、问题描述哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。

其压缩率通常在20%～90%之间。

哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。

一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。

有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。

若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。

前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。

这种编码称为前缀码。

编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。

译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。

为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。

从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。

图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。

在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。

每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。

给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。

C的一个前缀码编码方案对应于一棵二叉树T。

字符c在树T中的深度记为d T(c)。

d T(c)也是字符c的前缀码长。

则平均码长定义为：使平均码长达到最小的前缀码编码方案称为C的最优前缀码。

"2、构造哈弗曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。

其构造步骤如下：(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。

(2)算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。

(3)假设编码字符集中每一字符c的频率是f(c)。

以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。

一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。

经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。

构造过程如图所示：具体代码实现如下：(1)，程序主文件1.>2.eight = f[i];3. w[i].tree = z;4. }5.6.//建优先队列7. MinHeap<Huffman<Type>> Q(n);8.for(int i=1; i<=n; i++) (w[i]);9.10.//反复合并最小频率树11. Huffman<Type> x,y;12.*13.for(int i=1; i<n; i++)14. {15. x = ();16. y = ();17. (0,,;18. += ;19. = z;20. (x);21. }23.|24. x = ();25.26.delete[] w;27.28.return ;29.}(2) 二叉树实现1.#include<iostream>ing namespace std;3.~4.5.template<class T>6.struct BTNode7.{8. T data;9. BTNode<T> *lChild,*rChild;10.11. BTNode()12. {13. lChild=rChild=NULL;14.'15. }16.17. BTNode(const T &val,BTNode<T> *Childl=NULL,BTNode<T> *Childr=NULL)18. {19. data=val;20. lChild=Childl;21. rChild=Childr;22. }23.24. BTNode<T>* CopyTree()25.·26. {27. BTNode<T> *nl,*nr,*nn;28.29.if(&data==NULL)30.return NULL;31.32. nl=lChild->CopyTree();33. nr=rChild->CopyTree();35. nn=new BTNode<T>(data,nl,nr);36.《37.return nn;38. }39.};40.41.42.template<class T>43.class BinaryTree44.{45.public:46. BTNode<T> *root;47.·48. BinaryTree();49. ~BinaryTree();50.51.void Pre_Order();52.void In_Order();53.void Post_Order();54.55.int TreeHeight()const;56.int TreeNodeCount()const;57.58.；59.void DestroyTree();60.void MakeTree(T pData,BinaryTree<T> leftTree,BinaryTree<T> rightTree);61.void Change(BTNode<T> *r);62.63.private:64.void Destroy(BTNode<T> *&r);65.void PreOrder(BTNode<T> *r);66.void InOrder(BTNode<T> *r);67.void PostOrder(BTNode<T> *r);68.69.，70.int Height(const BTNode<T> *r)const;71.int NodeCount(const BTNode<T> *r)const;72.};73.74.template<class T>75.BinaryTree<T>::BinaryTree()76.{77. root=NULL;79.80.&81.template<class T>82.BinaryTree<T>::~BinaryTree()83.{84.85.}86.87.template<class T>88.void BinaryTree<T>::Pre_Order()89.{90. PreOrder(root);91.,92.}93.94.template<class T>95.void BinaryTree<T>::In_Order()96.{97. InOrder(root);98.}99.100.template<class T>101.void BinaryTree<T>::Post_Order() 102.—103.{104. PostOrder(root);105.}106.107.template<class T>108.int BinaryTree<T>::TreeHeight()const 109.{110.return Height(root);111.}112.113.、114.template<class T>115.int BinaryTree<T>::TreeNodeCount()const 116.{117.return NodeCount(root);118.}119.120.template<class T>121.void BinaryTree<T>::DestroyTree()123. Destroy(root);124.，125.}126.127.template<class T>128.void BinaryTree<T>::PreOrder(BTNode<T> *r)129.{130.if(r!=NULL)131. {132. cout<<r->data<<' ';133. PreOrder(r->lChild);134. PreOrder(r->rChild);135.~136. }137.}138.139.template<class T>140.void BinaryTree<T>::InOrder(BTNode<T> *r)141.{142.if(r!=NULL)143. {144. InOrder(r->lChild);145. cout<<r->data<<' ';146.—147. InOrder(r->rChild);148. }149.}150.151.template<class T>152.void BinaryTree<T>::PostOrder(BTNode<T> *r)153.{154.if(r!=NULL)155. {156. PostOrder(r->lChild);157."158. PostOrder(r->rChild);159. cout<<r->data<<' ';160. }161.}162.163.template<class T>164.int BinaryTree<T>::NodeCount(const BTNode<T> *r)const 165.{166.if(r==NULL)167.return 0;168.￥169.else170.return 1+NodeCount(r->lChild)+NodeCount(r->rChild);171.}172.173.template<class T>174.int BinaryTree<T>::Height(const BTNode<T> *r)const175.{176.if(r==NULL)177.return 0;178.else179.?180. {181.int lh,rh;182. lh=Height(r->lChild);183. rh=Height(r->rChild);184.return 1+(lh>rhlh:rh);185. }186.}187.188.template<class T>189.void BinaryTree<T>::Destroy(BTNode<T> *&r)190.-191.{192.if(r!=NULL)193. {194. Destroy(r->lChild);195. Destroy(r->rChild);196.delete r;197. r=NULL;198. }199.}200.201.#202.template<class T>203.void BinaryTree<T>::Change(BTNode<T> *r)//将二叉树bt所有结点的左右子树交换204.{205. BTNode<T> *p;206.if(r){207. p=r->lChild;208. r->lChild=r->rChild;209. r->rChild=p; //左右子女交换210. Change(r->lChild); //交换左子树上所有结点的左右子树211. Change(r->rChild); //交换右子树上所有结点的左右子树212.~213. }214.}215.216.template<class T>217.void BinaryTree<T>::MakeTree(T pData,BinaryTree<T> leftTree,BinaryTree<T> rightTree) 218.{219. root = new BTNode<T>();220. root->data = pData;221. root->lChild = ;222. root->rChild = ;223.]224.}(3) 最小堆实现1.#include <iostream>ing namespace std;3.template<class T>4.class MinHeap5.{6.private:7. T *heap; //元素数组，0号位置也储存元素8.！9.int CurrentSize; //目前元素个数10.int MaxSize; //可容纳的最多元素个数11.12.void FilterDown(const int start,const int end); //自上往下调整，使关键字小的节点在上13.void FilterUp(int start); //自下往上调整14.15.public:16. MinHeap(int n=1000);17. ~MinHeap();18.bool Insert(const T &x); //插入元素19.|20.21. T RemoveMin(); //删除最小元素22. T GetMin(); //取最小元素23.24.bool IsEmpty() const;25.bool IsFull() const;26.void Clear();27.};28.29.template<class T>30.，31.MinHeap<T>::MinHeap(int n)32.{33. MaxSize=n;34. heap=new T[MaxSize];35. CurrentSize=0;36.}37.38.template<class T>39.MinHeap<T>::~MinHeap()40.{41.！42.delete []heap;43.}44.45.template<class T>46.void MinHeap<T>::FilterUp(int start) //自下往上调整47.{48.int j=start,i=(j-1)/2; //i指向j的双亲节点49. T temp=heap[j];50.51.while(j>0)52.]53. {54.if(heap[i]<=temp)55.break;56.else57. {58. heap[j]=heap[i];59. j=i;60. i=(i-1)/2;61. }62. }63.'64. heap[j]=temp;65.}66.67.template<class T>68.void MinHeap<T>::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上69.{70.int i=start,j=2*i+1;71. T temp=heap[i];72.while(j<=end)73. {74.]75.if( (j<end) && (heap[j]>heap[j+1]) )76. j++;77.if(temp<=heap[j])78.break;79.else80. {81. heap[i]=heap[j];82. i=j;83. j=2*j+1;84. }85.*86. }87. heap[i]=temp;88.}89.90.template<class T>91.bool MinHeap<T>::Insert(const T &x)92.{93.if(CurrentSize==MaxSize)94.return false;95.96.$97. heap[CurrentSize]=x;98. FilterUp(CurrentSize);99.100. CurrentSize++;101.return true;102.}103.104.template<class T>105.T MinHeap<T>::RemoveMin( )106.{107.…108. T x=heap[0];109. heap[0]=heap[CurrentSize-1];110.111. CurrentSize--;112. FilterDown(0,CurrentSize-1); //调整新的根节点113.114.return x;115.}116.117.template<class T>118.!119.T MinHeap<T>::GetMin()120.{121.return heap[0];122.}123.124.template<class T>125.bool MinHeap<T>::IsEmpty() const126.{127.return CurrentSize==0;128.}129.130.template<class T>131.bool MinHeap<T>::IsFull() const132.{133.return CurrentSize==MaxSize;134.}135.136.template<class T>137.void MinHeap<T>::Clear()138.{139. CurrentSize=0;140.}3、贪心选择性质二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。