我不明白這個霍夫曼算法的實現

template<class T> 
    void huffman(MinHeap<TreeNode<T>*> heap, int n) 
    { 
     for(int i=0;i<n-1;i++) 
     { 
     TreeNode<T> *first = heap.pop(); 
     TreeNode<T> *second = heap.pop(); 
     TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data, second.data); 
     heap.push(bt); 
     } 
    }

在我的Fundamentals of Data Structures in C++教科書中，它給出了一個2頁的霍夫曼編碼定義和上面的代碼。對我來說，這本書還不夠詳細，所以我完成了Google搜索，並且瞭解了霍夫曼編碼的過程。該教科書聲稱，在上面的代碼的末尾，製作了霍夫曼樹。但對我來說，這似乎是錯誤的，因爲霍夫曼樹不需要一棵完整的樹，但上面的代碼似乎總是給出一棵完整的樹，因爲heap.push()。那麼有人可以向我解釋這段代碼沒有錯嗎？我不明白這個霍夫曼算法的實現

來源

2010-07-16 user299648

堆的樹結構不一定與生成的霍夫曼樹相匹配 - 相反，堆包含部分霍夫曼樹的森林，最初每個樹都包含一個符號節點。循環然後重複使用權重最小的兩個節點，將它們組合成一個節點，並將得到的組合節點放回。在這個過程結束時，堆包含一棵完成的樹。

來源

2010-07-16 23:47:37

然後我得不到的是，如果堆不一定是哈夫曼樹，我怎麼能遍歷或使用堆找到正確的葉節點。 – user299648 2010-07-17 00:09:59

堆是一種臨時輔助數據結構，用於提高查找權重最小的兩個霍夫曼節點的操作效率。最後，堆只包含一個元素，一個'BinaryTreeNode '，它可以彈出，然後是完成的霍夫曼樹的根;堆可以被銷燬，因爲它不再需要。 – 2010-07-17 00:20:41

非常感謝你！你真的很有幫助。 – user299648 2010-07-17 00:26:16

霍夫曼編碼通過在每一步取兩個最低值項來工作。當你第一次調用函數時（因爲你的MinHeap按值排序），兩個最低值項被彈出並「合併」到一個決策節點中，然後放回到堆中。該節點通過其子分數的總和進行評分並放回堆中。將它插回到堆中，根據它的分數將它放入正確的位置;如果它仍然比其他任何項目都低，那麼它將會在其他地方。

所以這個算法從底層開始構建樹，當你清空堆的時候，你將擁有一棵完整的樹。雖然我不明白'n'是什麼意思，該循環應該是while (heap.size() > 1)。無論如何，樹不是「滿的」，根據初始堆中項目的頻率如何得分，不同的分支將會有不同的長度。

來源

2010-07-16 23:49:02

我不明白這個霍夫曼算法的實現

回答

相關問題