哈夫曼編碼變體：Hyperhuffman 問題 — 優先隊列實現與長度計算

哈夫曼編碼變體：Hyperhuffman 問題解析

來源：ACM/ICPC 區域賽 / POJ / ZOJ — C - Hyperhuffman
任務：給定 N (≤ 500,000) 個字符的出現次數 P_i（已按非遞增排序），計算哈夫曼編碼後的總位元長度。

標準哈夫曼 vs Hyperhuffman

關鍵洞察

每次合併兩最小節點 p1, p2：

• 新頻率 v = p1.v + p2.v
• 新累積代價 sum = p1.sum + p2.sum + p1.v + p2.v

因為新節點深度比兩子樹各深 1，所以所有葉子編碼長度 +1，總長度增加 p1.v + p2.v。遞歸累加即得 sum。

算法流程

1. 讀入 N，將 N 個 P_i 作為初始節點 (v=P_i, sum=0) 推入 最小堆（優先隊列，按 v 排序）。
2. 堆大小 > 1 時循環：
    彈出最小 p1, p2 → 合併生成 p → 推回堆。
3. 最後堆頂節點的 sum 即為答案。

C++ 參考實現 (優先隊列 + long long)

#include 
using namespace std;
using ll = long long;

struct Node {
    ll sum = 0;   // 累積代價
    ll v = 0;     // 頻率和
    bool operator<(const Node& o) const { return v > o.v; } // 最小堆
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        priority_queue pq;
        for (int i = 0; i < n; ++i) {
            Node nd; cin >> nd.v; pq.push(nd);
        }
        while (pq.size() > 1) {
            Node p1 = pq.top(); pq.pop();
            Node p2 = pq.top(); pq.pop();
            Node p;
            p.v = p1.v + p2.v;
            p.sum = p1.sum + p2.sum + p1.v + p2.v;
            pq.push(p);
        }
        cout << pq.top().sum << '\n';
    }
    return 0;
}

複雜度分析

優化技巧（針對已排序輸入）

輸入 P_i 已非遞增，可用 雙隊列法 將 O(N log N) 降為 O(N)：

1. 隊列 A：初始頻率（已排序）。
2. 隊列 B：合併生成的新節點（產生順序單調遞增）。
3. 每次從 A、B 隊頭取最小兩個（雙指針比較），合併後推入 B 尾部。

此法利用「合併產生的頻率單調遞增」性質，避免堆操作，極大提速。

樣例驗證

輸入:
3
1 1 4

過程:
初始: (1,0) (1,0) (4,0)
合併 1+1: v=2, sum=0+0+1+1=2  → 堆: (2,2) (4,0)
合併 2+4: v=6, sum=2+0+2+4=8  → 堆: (6,8)
答案: 8  ✓

常見坑點

• int 溢位：必須用 long long / int64_t。
• 輸入多組測試：題目隱含多測試用例，while(cin>>n) 循環讀取。
• 優先隊列比較器：C++ priority_queue 默認大頂堆，需 operator< 反向或用 greater<>。
• N=1 邊界：題目保證 N≥2，但代碼最好兼容。

小結

Hyperhuffman 在標準哈夫曼基礎上引入累積代價字段，將「葉子深度 × 頻率」的總和轉化為合併過程中的增量累加。結合已排序輸入的雙隊列 O(N) 優化，是大規模字符集編碼長度計算的標準解法。