構建典範霍夫曼樹的最有效（*）方法是什麼？

Question

假設A是一個數組，其中A [0]保存字母表的第0個字母的頻率。

什麼是最有效的（*）計算代碼長度的方法？不確定，但我想效率可以根據內存使用情況或所需步驟進行。

我感興趣的所有數組是L其中L[0]包含字母表的第0個字母的代碼長度（位數），其中代碼來自由A頻率陣列構建的規範霍夫曼樹。

Answer 1

如果頻率形成單調序列，即， A [0] < = A [1] < = ... < = A [n-1]或A [0]> = A [1]> = ...> = A [n-1]可以在O（n）時間和O（1）額外空間中生成最佳代碼長度。這個算法只需要2個簡單的遍歷數組，並且速度非常快。完整的描述在[1]中給出。

如果您的頻率沒有排序，首先需要對它們進行排序，然後應用上述算法。在這種情況下，時間複雜度爲O（n log n），需要一個由n個整數組成的輔助數組來存儲排序順序 - 空間複雜度O（n）。

[1]： 就地由阿利斯泰爾莫法特和Jyrki Katajainen，可在線最小冗餘碼的計算：http://www.diku.dk/~jyrki/Paper/WADS95.pdf