哈夫曼樹構造演算法

❶ 哈夫曼樹構造演算法中j<n+i是什麼意思

先看一下哈夫曼樹的構造規則是：
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

用數據表示哈夫曼樹的話，首先有n個權值點，其初始化就是從 0 到 n -1，先從這裡面查找兩個權值最小的結點，就是遍歷一遍，把最小的值取出來。X1 和X2 要記錄著兩個權值在哪個位置。
然後把這兩個權值加起來的和放回到數組n的位置，然後繼續遍歷這個數據，現在是從0 到n了，當然原來X1 和X2位置的兩個點不用管，已經有父節點了。繼續上述過程直到只有一個節點位置。

如 1 2 3 4 5 6構造哈夫曼樹，先初始化parent 為 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先從上述中選取兩個權值最小的節點 1 和 2，構造樹變為3，放到數組6的位置，原權值序列變為：
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到3 和 3，放到數組7的位置，權值序列變為：
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
繼續選取 兩個最小權值且parent為-1的點。找到4 和5，到數組8的位置，權值序列變為：
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到6 和6，到數組9的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到9 和12，到數組10的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
結束
所以你說的j < n + i，由於每次選取兩個權值的點權值和做為新的節點放在數組後面，當然下一次循環的時候要多一次循環。
X1 和X2要記錄下選擇兩個權值，將其父節點的位置設置為新的權值點位置。

❷ 哈夫曼樹的構造是什麼

哈夫曼樹構造：結構化的Huffman演算法生成的Huffman樹子樹都是有序的，所以一般生成Huffman樹時都為節點排序，即使這樣結果也不唯一。

哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。

歷史

1951年，哈夫曼在麻省理工學院（MIT）攻讀博士學位，他和修讀資訊理論課程的同學得選擇是完成學期報告還是期末考試。

導師羅伯特·法諾（Robert Fano）出的學期報告題目是：查找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。

哈夫曼使用自底向上的方法構建二叉樹，避免了次優演算法香農-范諾編碼（Shannon–Fano coding）的最大弊端──自頂向下構建樹。

1952年，於論文《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Rendancy Codes）中發表了這個編碼方法。