c++ - minheap を使用したハフマン ツリーの実装

Question

私がクラスで使用している本 (および他のいくつかの場所から見たものから) では、ハフマン木を作成するためのアルゴリズムは、

(1) 読み込まれているファイルまたは文字列の各文字の頻度に基づいて最小ヒープを構築します。

(2) minheap から 2 つの最小値を取り出し、それらの重みを新しいノードに結合します。

(3) 新しいノードを同じ最小ヒープに再挿入します。

ステップ 3 について混乱しています。私が見たほとんどのハフマン ツリーは、最小ヒープよりも最大ヒープに似た属性を持っています (完全なツリーではありませんが)。つまり、ルートには最大の重み (またはむしろ重みの組み合わせ) が含まれていますが、そのすべての子の重みはそれよりも小さくなっています。結合されたノードが最小ヒープに戻されるときに、この実装はどのようにハフマン ツリーを提供しますか? 私はしばらくこれに苦労してきました。

同様の質問がすでにここに投稿されています (私と同じ本で): I don't understand this Huffman algorithm implementation

（3）で説明されている正確な機能を見たい場合。

助けてくれてありがとう！

Answer 1

多くの場合、ハフマン ツリーは完全なバイナリ ツリーではないため、最小ヒープではありません。

ハフマン アルゴリズムは、ツリーが構築される周波数のリストとして簡単に理解できます。小さなブランチが最初に構築され、最終的にすべてが 1 つのツリーにマージされます。各リスト項目はシンボルとして始まり、その後、構築されたシンボルまたはサブツリーになる場合があります。各リスト項目には常に頻度があります (通常は整数のカウント)。

リストから最小の周波数を 2 つ取り出します (同順位は関係ありません。最適なコードが複数ある場合でも、どの選択でも最適なコードが得られます)。これら 2 つから単一レベルのバイナリ ツリーを構築します。ここで、2 つの葉はそれらの周波数のシンボルです。周波数を追加して、ツリーを表す新しい周波数を作成します。その周波数をリストに戻します。リストの頻度が 1 つ少なくなりました。

繰り返す。ここで、各ステップで構築されたバイナリ ツリーは、各ブランチにシンボル リーフ、または 1 つのリーフと以前に構築されたツリー、または 2 つのツリー (最初は 3 番目のステップ) を持つ場合があります。

リストに残る周波数が 1 つになるまで続けます。それはすべての元の周波数の合計になります。その周波数には、完全なハフマン ツリーが関連付けられています。

これで、(任意に) 0 と 1 を各バイナリ ブランチに割り当てることができます。ルートからシンボルまでツリーをトラバースすることで、コードを構築またはコードをデコードします。そのトラバースの分岐からのビットは、そのシンボルのハフマン コードです。