定义

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。 哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

步骤

求{11,8,6,5,2}构成的哈夫曼树的加权路径长度。 【思路】贪心：权值越小，距离根越远。永远让最小的两个数相加。

用原始数组构造小顶堆,res=0; 弹出堆顶两个最小值，和为sum，res+=sum； 将sum放入堆中，如果堆内元素大于1则转到步骤2，否则转到下一步； 堆中最后的树即为哈夫曼树的根，res即为加权路径长度。

加权路径长度：权值*路径数。权值就是结点值，路径数就是顶点到结点经历边的个数 。在这里就是：（8+11)x2+6x2+(2+5)x3=71

int WPLofHuffman(vector<int> &arr){ int res=0; int sum=0; priority_queue<int,vector<int>,greater<int>> minheap(arr.begin(),arr.end()); while(minheap.size()>1){ int tmp1=minheap.top(); minheap.pop(); int tmp2=minheap.top(); minheap.pop(); sum=tmp1+tmp2; res+=sum; minheap.push(sum); } return res; }

【构造哈夫曼树】

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} ~TreeNode(){ if(left) delete left; if(right) delete right; } }; struct cmp{ bool operator()(const TreeNode* a,const TreeNode* b){ return a->val>b->val; } }; class HuffmanTree{ public: TreeNode* root; int WPL=0; HuffmanTree(vector<int> &arr){ vector<TreeNode*> treearr; for(int num:arr) treearr.push_back(new TreeNode(num)); priority_queue<TreeNode*,vector<TreeNode*>,cmp> minheap(treearr.begin(),treearr.end()); while(minheap.size()>1){ TreeNode* tmp1=minheap.top(); minheap.pop(); TreeNode* tmp2=minheap.top(); minheap.pop(); int sum=tmp1->val+tmp2->val; WPL+=sum; TreeNode* node=new TreeNode(sum); node->left=tmp1; node->right=tmp2; minheap.push(node); } root=minheap.top(); } ~HuffmanTree(){ delete root; } };

参考： https://blog.csdn.net/HFish24/article/details/105031292/