[题解] 哈夫曼编码（附图分析）

“Don’t bark up the wrong Binary Tree.”

【问题描述】

　　我们称树的带权路径长度（WPL）最小的二叉树为“哈夫曼树”或“最优二叉树”。

　　哈夫曼树对字符进行编码，称为哈夫曼树编码(Huffman Coding)。哈夫曼编码是一种编码方式，哈夫曼编码是可变字长编码的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

　　现在给定 n 个字符在文章中出现的频率：W[1], W[2],…, W[n]，给每个字符赋予一个01串，使得任意一个字符的编码不是另一个字符编码的前缀（哈夫曼编码），而且编码的总长度（每个字符的频率于编码长度的乘积总和）尽量小。

【输入格式】

　　第一行是一个整数n，表示n个字符的出现频率。
　　以下n行，每行有三一个整数W[i]。
　　

【输出格式】

　　一个整数，表示n个字符的编码总长度。

【输入样例】

6
45
13
12
16
9
5

【输出样例】

224

【数据范围】

n<=40000，w[i]<=50000

---

一些小分析~

about题目样例：

不正经的公式证明（大概是这个意思就好了(￣▽￣)／）：

---

#include<algorithm>
#include<iostream>
#include<fstream>
#include<cstdio>
#include<queue>
using namespace std;

priority_queue<int,vector<int>, greater<int> > q;

int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        q.push(t);
    }

    long long sum=0; 
    while(!q.empty()){
        int not_leaf=0;

        if(q.size()>=2){
            //取两次最小值合成非叶节点 
            not_leaf+=q.top();
            q.pop();
            not_leaf+=q.top();
            q.pop();

            sum+=not_leaf;//sum(W[i]·P[l]=非叶节点权值和)
            q.push(not_leaf);   
        }
        else break;
    }
    printf("%lld",sum);
    return 0;
}

[转载请标明出处 , 谢谢]