資料結構中的 t 元樹霍夫曼演算法

一項簡單的演算法

• 準備一個包含 n 個初始霍夫曼樹的集合，其中每一個都是一個單葉節點。按權重（頻率）將 n 棵樹保留在優先順序佇列中。
• 移除或刪除前兩棵樹（權重最小的樹）。將這兩棵樹組合起來建立一個新樹，其根節點與兩棵樹相關聯作為子樹，且其權重是這兩個子樹權重之和。
• 將這棵新樹儲存在優先順序佇列中。
• 重複步驟 2-3，直到所有部分霍夫曼樹都合併到一棵樹中為止。

這是一個貪心演算法：每次迭代時，該演算法進行一個“貪婪”決策，合併具有最小權重的兩個子樹。演算法有可能提供所需的結果嗎？

• 引理：令 x 和 y 是兩個出現頻率最低的字元。存在一個最佳編碼樹，其中 x 和 y 是有著最小深度的兄弟節點，與樹中的其他葉節點相同。
• 定理：霍夫曼編碼被視為最佳無字首二進位制編碼（對於給定的字母集，貪心演算法構造霍夫曼樹，最小化外部路徑權重）。

Arnab Chakraborty

更新於： 2020 年 7 月 1 日

467 人次瀏覽

開啟您的 職業之旅

完成本課程可獲得認證

開始