算法導論：Huffman 編碼與 C++ 優先隊列實現

Huffman 編碼原理

給定字符及其權重（頻率），構建最優前綴編碼樹。算法：

1. 將每個字符作為葉子節點放入最小堆（優先隊列），鍵為權重。
2. 重複：取出權重最小的兩棵樹，合併為新樹，權重為兩者之和，放回堆。
3. 直到堆中剩一棵樹，即為 Huffman 樹。

編碼規則：左邊 0，右邊 1（或相反）。中序遍歷輸出編碼。

C++ 實現關鍵：自定義比較器

優先隊列存儲節點指針，需重載比較運算符使最小權重在隊首。

struct Node {
    int freq; char ch;
    Node *left, *right;
    Node(int f, char c) : freq(f), ch(c), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) { return a->freq > b->freq; } // 最小堆
};

Node* buildHuffman(priority_queue, Compare>& pq) {
    while (pq.size() > 1) {
        Node *l = pq.top(); pq.pop();
        Node *r = pq.top(); pq.pop();
        Node *parent = new Node(l->freq + r->freq, 0);
        parent->left = l; parent->right = r;
        pq.push(parent);
    }
    return pq.top();
}

void inorder(Node* root, string code) {
    if (!root) return;
    if (root->left) inorder(root->left, code + '0');
    if (!root->left && !root->right) cout << root->ch << ": " << code << endl;
    if (root->right) inorder(root->right, code + '1');
}

完整示例

輸入字符 a-f 及頻率 45,13,12,16,9,5，輸出編碼：a:0, b:101, c:100, d:111, e:1101, f:1100（可能因合併順序不同但等效）。