你滿心歡喜的召喚出了外星生物，以為可以變身超人擁有強大力量戰勝一切怪獸，然而面對著身前高大的外星生物你一臉茫然，因為，你懂M78星雲語嗎？不過不用擔心，因為零崎非常機智，他給出了關鍵性的提示：“講道理，日語可是全宇宙通用語，所以為什麼不試試和外星人講日語呢？”
不過現在外星生物說的話都是“!@#$%^&%#%I&!……”這樣的東西，你要怎麼轉換成日語呢？
作位全宇宙通用的日語，自然有一套萬能的轉換算法，那就是Huffman編碼轉換！當然了這肯定不是普通的Huffman編碼轉換，而是根據不同的編碼長度轉換為不同的假名。
第一行為一個整數t，接下來t行數據。1<=t<=100
每組輸入數據為一個外星語字符串，為了表示方便，暫時使用大小寫英文字母代替外星字母。字符串長度不超過2000
對於每組數據，輸出對應的二進制Huffman編碼總長度
2
abababac
abcdefg12 20
題目來源：http://biancheng.love/contest/23/problem/D/index
解題思路:在前面的哈夫曼樹構造以及哈夫曼編碼和解碼時，已經講述了哈夫曼編碼的方式。現在我們需要得到哈夫曼編碼的長度。回憶一下在解碼過程中的算法，如果是0向左搜索，如果是1向右搜索。因此一個字符在一個構造好的哈夫曼樹中都是居於葉子結點。意思就是樹的各個分叉的最低端。因此每個字符的長度也就是該字符在哈夫曼樹中的深度。希望能夠理解這一點。
在明白字符長度就是字符深度之後開始重新分析一下哈夫曼的樹的構造過程。哈夫曼樹的建立時通過對每個字符出現頻率的統計來設計的，不同的出現頻率會對應不同的深度也就是不同的長度。
建立過程如下：
1、取出頻率最小的兩個數，將這兩個數按照最優二叉樹的規則（左孩子<父節點<右孩子）得到父節點的值，將這個值放到上述頻率中（相當於合並了兩個最小的兩個頻率）
2、按照上述規則進行反復合並與放回。
3、得到哈夫曼樹。
通過上述分析得到每次需要得到兩個最小的頻率。怎樣才能實現每次得到最小的兩個頻率呢？可以通過數組，但是每次都要排序，很麻煩也很費時間；可以使用第i個順序統計量的隨機算法，但是其復雜度也是很高的。那我們可以選用什麼結構呢？這時候就到了之前講過的優先隊列
使用優先隊列的過程：
1、首先需要統計字符串中每個字母的出現頻率，由於題目中已經簡化問題，將字符限制在小寫字符a到小寫字符z,
2、初始化a到z的出現頻率為0，所以在統計完頻率頻率之後需要借助頻率不為0這一重要條件將出現的字符push進入隊列。
3、每次取出最小的兩個相加之後再放入優先隊列。退出循環的條件為優先隊列為空。
下面給出本題代碼：
#include <bits/stdc++.h>
#define max_size 10010
using namespace std;
typedef long long LL;
char c[max_size];
long long f[max_size];
priority_queue<LL ,vector<LL>,greater<LL> >q;//建立小頂堆；
long long n,ans;
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
string s;
cin>>s;
getchar();
memset(f,0,sizeof(f));
int lens=s.size();
for(int i=1; i<=lens; i++)
{
c[i]=s[i-1];
f[c[i]]++;
}
while(!q.empty())
q.pop();
for(int i=65; i<=122; i++)
{
if(f[char(i)]>0)
{
sum++;
q.push(f[char(i)]);
}
}
ans=0;
while(q.size()>1)
{
LL a=q.top();
q.pop();
LL b=q.top();
q.pop();
ans+=(a+b); // 因為編碼長度和其在樹中的層數相關
q.push(a+b);
}
printf("%lld\n",ans);
}
return 0;
}
可以發現在前面的統計頻率不僅僅是為了統計頻率，同時也是實現了將其push進優先隊列。
下面給出按照哈夫曼樹解決問題的代碼，可以比較兩種方法的優缺點:
