# 霍夫曼編碼（Huffman Encoding）
:::spoiler
1. 這是貪婪演算法的經典問題，已知每個字元的出現頻率，經由霍夫曼編碼可以求得最短的編碼結果，霍夫曼編碼使用可以變動長度的$0$與$1$數字進行編碼。
2. 本題融合之後的樣板函式庫（STL）、樹狀結構與深度優先搜尋章節，可以先瞭解概念部分，若程式看不懂可以先跳過，等熟悉樣板函式庫（STL）、樹狀結構與深度優先搜尋等概念後，再回來複習程式碼。
:::

### 輸入說明
每次輸入數字$n$，$n$表示字元個數，輸入$n$小於$26$，之後有$n$ 行分別是每一行為一個小寫英文字母與一個整數組成，小寫英文字母表示被編碼的字元，而整數表示出現的頻率，數值越大表示頻率越高。

### 輸出說明
輸出每個小寫英文字母的編碼。

### 輸入輸出範例
輸入範例
5
a 10
b 4
c 5
d 7
e 8

輸出範例
d 00
e 01
b 100
c 101
a 11

### 解題構思
1. 貪婪準則是先將所有字元依照出現頻率的由小到大進行排序。
2. 優先考慮出現頻率最低的兩個字元，組合成新的節點，此節點的頻率為兩個目前最小字元頻率的加總，將此節點重新加入所有字元的排序。
3. 再取出最小的兩個字元或節點，組合成新的節點，此節點的頻率為兩個目前最小字元頻率的加總，將此節點重新加入所有字元的排序。
4. 如此不斷重複，直到最後剩下一個節點。
5. 編碼為最上層的左邊編碼$0$而右邊編碼$1$，從上到下重複左邊編碼$0$而右邊編碼$1$，直到無法下去為止，越下面字元編碼越長。

#include <iostream>
#include <algorithm>       // for sort()
#include <deque>         // for deque object, front(), pop_front()

using namespace std;

const int MAXN = 100+5;//最大字元數量

//自訂huffman tree 的節點(node)的資料型態
typedef struct _node{
    int id;             // node 編碼
    char ch;            // node 字元
    int weight;         // node 權重
    bool isSrc;         // node 是否為原始節點
    int left;           // node 的左邊的node編號
    int right;          // node 的右邊的node編號
}NODE;
NODE nodes[MAXN]; // 儲存輸入node的陣列

deque<NODE> myQue; //儲存 huttman tree node資料
    

int main(){
    /* 輸入&排序 */
    int n;  // 字元個數
    tmp.clear();    // 請空tmp
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>nodes[i].ch>>nodes[i].fre;
        nodes[i].id=i;
        nodes[i].isLeaf=1;
        tmp.push_back(nodes[i]);
    }
    sort(tmp.begin(),tmp.end(),cmp);

    /* 處理 */
    int newID=n;    // 新NODE的ID從n開始
    while(tmp.size()>1){
        NODE x=tmp.front();  // tmp中fre最小元素
        tmp.pop_front();
        NODE y=tmp.front();  // tmp中fre次小元素
        tmp.pop_front();

        NODE z;
        z.id=newID;
        z.fre=x.fre+y.fre;  // 兩fre相加
        z.isLeaf=0;
        z.lefID=x.id;
        z.rigID=y.id;
        nodes[newID]=z; //將x+y加入nodes
        tmp.push_back(z);   // 將x+y加入tmp
        sort(tmp.begin(),tmp.end(),cmp);
        newID++;
    }

    dfs(tmp.front().id,0);
}

bool cmp(NODE p,NODE q){
    return p.fre<q.fre; // 按fre(頻率)由小到大排列
}
char res[20];

void dfs(int topID,int level){
    if(!nodes[topID].isLeaf){
        res[level]='0';
        dfs(nodes[topID].lefID,level+1);
        res[level]='1';
        dfs(nodes[topID].rigID,level+1);
    }else{
        cout<<nodes[topID].ch<<" ";
        for(int i=0;i<level;i++) cout<<res[i];
        cout<<"\n";
    }
}