ハッシュテーブルを使用してツリー内のノードを追跡するにはどうすればよいですか？

Question

フィボナッチヒープを実装しようとしています。後続の操作のためにノードを追跡する必要があります。 未初期化の場合、フィボナッチヒープは、m度のツリーまたは構造内の最大ノードへのポインタを持つツリーの集合と考えることができます。 ツリー構造は単語とその頻度を入力とし、頻繁に出現する単語を出力として与える必要があります。 例えば、 入力：ハッシュテーブルの

Ann 31 
Dustin 27 
Ryan 43 
Ashley 13 
Sunday 23 
Tuesday 19 
2 //Output two top most occurring words in the tree 

Output: 
Ryan, Ann 

私の理解では、非常に初歩的です。単語をキーとして入力し、出力としてハッシュ値を出力します。この出力を、その周波数を格納するツリー内の対応するノードへのポインタにするにはどうすればよいですか？ また、頻繁に出現する単語「n」を見つけるための入力があると、先頭のノード「n」回を繰り返し削除して構造体に再挿入できますか？または、ソートされたハッシュテーブルを保持する方がよいでしょうか？

Answer 1

これまでのコードのうちの1つをコーディングしている人物として、あなたがやろうとしていることを実行できる方法がいくつかあります。

1. 構造体内のノードへのポインタを返すようにしてから、補助ハッシュテーブルを使用してこれらのポインタを格納します。挿入を行うには、キーとその優先順位を挿入し、フィボナッチヒープ内のノードへのポインタを手渡してから、キーとポインタを外部ハッシュテーブルに追加します（Javaの場合は、HashMap; C++では、 std::unordered_mapのようなものです;私は自分自身を巻き込むことに反対してください）。

2. フィボナッチヒープに格納する各キーを実際に完全なノード構造にすることで、侵入型のデータ構造を使用します。フィボナッチヒープを実装すると、入力の関連フィールドを上書きしてヒープ構造に配線し、必要に応じてノードを保存することができます。

個人的には、オプション（1）はほとんどのアプリケーションでオプション（2）よりもきれいだと思っていますが、（2）を超える理由があります。

メタノーでは、フィボナッチヒープはコード化が難しく、実際には多くのユースケースで漸近的に高速であるにもかかわらずバイナリヒープよりも大幅に遅いことが知られています。あなたがそうしなければならない魅力的な理由がない限り、実際には1つを使用することに反対することをお勧めします。